开发者社区云计算文章正文

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

2022-05-23 113

版权

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

简介： 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 代码

voidShortestDist( MGraphGraph, intdist[], intpath[], VertexS )
{
intvis[MaxVertexNum], num[MaxVertexNum];
for(inti=0;i<Graph->Nv;i++) num[i]=vis[i]=0, dist[i]=INFINITY, path[i]=-1;
dist[S]=0;
while(1)
    {
intmi=INFINITY; S=-1;
for(inti=0;i<Graph->Nv;i++)
if(!vis[i] &&mi>dist[i]) mi=dist[i], S=i;
if(S==-1) break;
vis[S]=1;
for(inti=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;
            }
elseif(!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(inti=0;i<MaxVertexNum;i++)
if(INFINITY==dist[i]) dist[i]=-1;
}