开发者社区> Lux_Sun> 正文

Data Structures and Algorithms (English) - 6-17 Shortest Path [4](25 分)

简介: Data Structures and Algorithms (English) - 6-17 Shortest Path [4](25 分)
+关注继续查看

题目链接:点击打开链接


题目大意:略。


解题思路:注意:因为一开始 mi==0 导致 0+无法到达的点(INF)==INF==dist[i],s.t. num[i]、path[i] 误被更新,所以需要再加个判断条件——“Graph->G[S][i]!=INFINITY”,这样也省了再末尾重新更新。


AC 代码

void ShortestDist( MGraph Graph, int dist[], int path[], Vertex S )
{
    int vis[MaxVertexNum], num[MaxVertexNum];
    for(int i=0;i<Graph->Nv;i++) num[i]=vis[i]=0, dist[i]=INFINITY, path[i]=-1;
    dist[S]=0;
 
    while(1)
    {
        int mi=INFINITY; S=-1;
        for(int i=0;i<Graph->Nv;i++)
            if(!vis[i] && mi>dist[i]) mi=dist[i], S=i;
 
        if(S==-1) break;
        vis[S]=1;
 
        for(int i=0;i<Graph->Nv;i++)
        {
            if(!vis[i] && Graph->G[S][i]+mi<dist[i])
            {
                dist[i]=Graph->G[S][i]+mi;
                num[i]=num[S]+1;
                path[i]=S;
            }
            else if(!vis[i] && Graph->G[S][i]+mi==dist[i] && Graph->G[S][i]!=INFINITY)
            {
                if(num[S]+1<num[i])
                {
                    num[i]=num[S]+1;
                    path[i]=S;
                }
            }
        }
    }
 
    for(int i=0;i<MaxVertexNum;i++)
        if(INFINITY==dist[i]) dist[i]=-1;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
+关注
2689
文章
1
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载