资源描述：
《应用dijkstra算法求赋权图最短路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、给出赋权图,如下图所示：应用Dijkstra算法，求出顶点A到其它各点的最短距离，MATLAB源程序m文件清单如下：w=[01inf2infinf1034infinfinf3012224103infinfinf2302infinf2inf20];%图的矩阵存储n=6;%顶点数目Result=inf(n-1,n+1);%保存寻找第一个顶点到其余顶点最短路径的中间结果fori=1:n-1Result(1,i)=w(1,i+1);endfori=2:n-1ValMin=inf;IndMin=1;forj=1:n-1ifValMin>Result(i-1
2、,j)ValMin=Result(i-1,j);IndMin=j;endendResult(i-1,n)=IndMin;Result(i-1,n+1)=ValMin;forj=1:n-1DelFlag=false;fork=1:i-1ifj==Result(k,n)DelFlag=true;endendifDelFlag==falseifResult(i-1,j)>Result(i-1,n+1)+w(Result(i-1,n)+1,j+1)Result(i,j)=Result(i-1,n+1)+w(Result(i-1,n)+1,j+1);els
3、eResult(i,j)=Result(i-1,j);endendendendValMin=inf;IndMin=1;forj=1:n-1ifValMin>Result(n-1,j)ValMin=Result(n-1,j);IndMin=j;endendResult(n-1,n)=IndMin;Result(n-1,n+1)=ValMin;ValueRoute=inf(n-1,n);%保存用标号表示的第一个顶点到其余顶点的最短路径和最短距离fori=1:n-1j=1;whileResult(j,n)~=ij=j+1;endIndRoute=n-1
4、;ValueRoute(i,IndRoute)=Result(j,n);ValueRoute(i,n)=Result(j,n+1);ValMin=Result(j,n+1);IndMin=Result(j,n);IndRoute=IndRoute-1;whileResult(j,n)>1j=j-1;ifResult(j,IndMin)>ValMin;ValueRoute(i,IndRoute)=Result(j,n);IndRoute=IndRoute-1;ValMin=Result(j,n+1);IndMin=Result(j,n);enden
5、dendStringRoute.Route='A';%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短路径StringRoute.Distance=0;%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短距离k=2;fori=1:n-1switchValueRoute(1,i)case1StringRoute.Route(k)='B';k=k+1;case2StringRoute.Route(k)='C';k=k+1;case3StringRoute.Route(k)='D';k=k+
6、1;case4StringRoute.Route(k)='E';k=k+1;case5StringRoute.Route(k)='F';k=k+1;otherwisecontinue;end%对于顶点数目不同并且顶点表示方式不同的图要相应修改CASE语句个数和分支语句endStringRoute.Distance=ValueRoute(1,n);CharRoute=[StringRoute];forj=2:n-1StringRoute.Route='A';%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短路径k=2
7、;fori=1:n-1switchValueRoute(j,i)case1StringRoute.Route(k)='B';k=k+1;case2StringRoute.Route(k)='C';k=k+1;case3StringRoute.Route(k)='D';k=k+1;case4StringRoute.Route(k)='E';k=k+1;case5StringRoute.Route(k)='F';k=k+1;otherwisecontinue;end%对于顶点数目不同并且顶点表示方式不同的图要相应修改CASE语句个数和分支语句endS
8、tringRoute.Distance=ValueRoute(j,n);CharRoute=[CharRoute;StringRoute
