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

给出赋权图,如下图所示：
应用Dijkstra算法，求出顶点A到其它各点的最短距离，MATLAB源程序m文件清单如下：
w=[01inf2infinf
1034infinf
inf30122
24103inf
infinf2302
infinf2inf20];%图的矩阵存储
n=6;%顶点数目
Result=inf(n-1,n+1);%保存寻找第一个顶点到其余顶点最短路径的中间结果
fori=1:n-1
Result(1,i)=w(1,i+1);
end
fori=2:n-1
ValMin=inf;IndMin=1;
forj=1:n-1
ifValMin>Result(i-1,j)
ValMin=Result(i-1,j);
IndMin=j;
end
end
Result(i-1,n)=IndMin;Result(i-1,n+1)=ValMin;
forj=1:n-1
DelFlag=false;
fork=1:i-1
ifj==Result(k,n)
DelFlag=true;
end
end
ifDelFlag==false
ifResult(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);
else
Result(i,j)=Result(i-1,j);
end
end
end
end
ValMin=inf;IndMin=1;
forj=1:n-1
ifValMin>Result(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);%保存用标号表示的第一个顶点到其余顶点的最短路径和最短距离
fori=1:n-1
j=1;
whileResult(j,n)~=i
j=j+1;
end
IndRoute=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)>1
j=j-1;
ifResult(j,IndMin)>ValMin;
ValueRoute(i,IndRoute)=Result(j,n);
IndRoute=IndRoute-1;
ValMin=Result(j,n+1);
IndMin=Result(j,n);
end
end
end
StringRoute.Route='A';%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短路径
StringRoute.Distance=0;%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短距离
k=2;
fori=1:n-1
switchValueRoute(1,i)
case1
StringRoute.Route(k)='B';
k=k+1;
case2
StringRoute.Route(k)='C';
k=k+1;
case3
StringRoute.Route(k)='D';
k=k+1;
case4
StringRoute.Route(k)='E';
k=k+1;
case5
StringRoute.Route(k)='F';
k=k+1;
otherwise
continue;
end
%对于顶点数目不同并且顶点表示方式不同的图要相应修改CASE语句个数和分支语句
end
StringRoute.Distance=ValueRoute(1,n);
CharRoute=[StringRoute];
forj=2:n-1
StringRoute.Route='A';%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短路径
k=2;
fori=1:n-1
switchValueRoute(j,i)
case1
StringRoute.Route(k)='B';
k=k+1;
case2
StringRoute.Route(k)='C';
k=k+1;
case3
StringRoute.Route(k)='D';
k=k+1;
case4
StringRoute.Route(k)='E';
k=k+1;
case5
StringRoute.Route(k)='F';
k=k+1;
otherwise
continue;