《应用dijkstra算法求赋权图最短路径》由会员分享，可在线阅读，更多相关《应用dijkstra算法求赋权图最短路径（4页珍藏版）》请在金锄头文库上搜索。
1、给出赋权图,如下图所示：应用 Dijkstra 算法，求出顶点 A 到其它各点的最短距离，MATLAB 源程序 m 文 件清单如下： w=0 1 inf 2 inf inf1 0 3 4 inf infinf 3 0 1 2 22 4 1 0 3 infinf inf 2 3 0 2inf inf 2 inf 2 0;%图的矩阵存储 n=6;%顶点数目 Result=inf(n-1,n+1);%保存寻找第一个顶点到其余顶点最短路径的中间结果 for i=1:n-1Result(1,i)=w(1,i+1); end for i=2:n-1ValMin=inf;IndMin=1;for j=1:n
2、-1if ValMinResult(i-1,j)ValMin=Result(i-1,j);IndMin=j;endendResult(i-1,n)=IndMin;Result(i-1,n+1)=ValMin;for j=1:n-1 DelFlag=false;for k=1:i-1if j=Result(k,n)DelFlag=true;end4DABFEC31223212endif DelFlag=falseif Result(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-
3、1,n)+1,j+1);elseResult(i,j)=Result(i-1,j);endendend end ValMin=inf;IndMin=1; for j=1:n-1if ValMinResult(n-1,j)ValMin=Result(n-1,j);IndMin=j;end end Result(n-1,n)=IndMin;Result(n-1,n+1)=ValMin;ValueRoute=inf(n-1,n);%保存用标号表示的第一个顶点到其余顶点的最短路径和最短距离 for i=1:n-1j=1;while Result(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;while Result(j,n)1j=j-1;if Result(j,IndMin)ValMin;ValueRoute(i,IndRoute)=Result(j,n);IndRoute=IndRoute-1;ValMin=Result(j,n+1);IndMin=Result(j,n);endend endStringRoute.Route=A
5、;%结构 StringRoute 的 Route 域依次临时存储从第一个顶点到其 余顶点的最短路径 StringRoute.Distance=0;%结构 StringRoute 的 Route 域依次临时存储从第一个顶点到其余顶 点的最短距离 k=2; for i=1:n-1switch ValueRoute(1,i)case 1StringRoute.Route(k)=B;k=k+1;case 2StringRoute.Route(k)=C;k=k+1;case 3StringRoute.Route(k)=D;k=k+1;case 4StringRoute.Route(k)=E;k=k+1;
6、case 5StringRoute.Route(k)=F;k=k+1;otherwisecontinue;end%对于顶点数目不同并且顶点表示方式不同的图要相应修改 CASE 语句个数和分支语句 end StringRoute.Distance=ValueRoute(1,n); CharRoute=StringRoute; for j=2:n-1StringRoute.Route=A ;%结构 StringRoute 的 Route 域依次临时存储从第一个顶点 到其余顶点的最短路径k=2;for i=1:n-1switch ValueRoute(j,i)case 1StringRoute.Ro
7、ute(k)=B;k=k+1;case 2StringRoute.Route(k)=C;k=k+1;case 3StringRoute.Route(k)=D;k=k+1;case 4StringRoute.Route(k)=E;k=k+1;case 5StringRoute.Route(k)=F;k=k+1;otherwisecontinue;end%对于顶点数目不同并且顶点表示方式不同的图要相应修改 CASE 语句个数和分支语句endStringRoute.Distance=ValueRoute(j,n);CharRoute=CharRoute;StringRoute; endfprintf(A 点到其余 5 个顶点的最短距离和最短路径如下：n) for i=1:n-1disp(CharRoute(i) end
