应用Dijkstra算法求赋权图最短路径.doc

应用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,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);elseResult(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;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);='A';%=0;%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短距离k=2;fori=1:n-1switchValueRoute(1,i)(k)='B';k=k+1;(k)='C';k=k+1;(k)='D';k=k+1;(k)='E';