给出赋权图,如下图所示：
应用Dijkstra 算法，求出顶点A到其它各点的最短距离，MATLAB源程序m文件清单如下：
w=[0 1 inf 2 inf inf
1 0 3 4 inf inf
inf 3 0 1 2 2
2 4 1 0
3 inf
inf inf 2 3 0 2
inf inf 2 inf 2 0];%图的矩阵存储
n=6;%顶点数目
Result=inf(n-1,n+1);%保存寻找第一个顶点到其余顶点最短路径的中间结果
for i=1:n-1
Result(1,i)=w(1,i+1);
end
for i=2:n-1
ValMin=inf;IndMin=1;
for j=1:n-1
if ValMin>Result(i-1,j)
ValMin=Result(i-1,j);
IndMin=j;
end
end
Result(i-1,n)=IndMin;Result(i-1,n+1)=ValMin;
for j=1:n-1
DelFlag=false;
for k=1:i-1
if j==Result(k,n)
DelFlag=true;
end
if DelFlag==false
if 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-1,n)+1,j+1);
else
Result(i,j)=Result(i-1,j);
end
end
end
end
ValMin=inf;IndMin=1;
for j=1:n-1
if ValMin>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);%保存用标号表示的第一个顶点到其余顶点的最短路径和最短距离
for i=1:n-1
j=1;
while Result(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;
while Result(j,n)>1
j=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);
end
end
end
StringRoute.Route='A ';%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短路径
StringRoute.Distance=0;%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短距离
k=2;
for i=1:n-1
switch ValueRoute(1,i)
StringRoute.Route(k)='B';
k=k+1;
case 2
StringRoute.Route(k)='C';
k=k+1;
case 3
StringRoute.Route(k)='D';
k=k+1;
case 4
StringRoute.Route(k)='E';
k=k+1;
case 5
StringRoute.Route(k)='F';
k=k+1;
otherwise
continue;
end
%对于顶点数目不同并且顶点表示方式不同的图要相应修改CASE语句个数和分支语句end
StringRoute.Distance=ValueRoute(1,n);
CharRoute=[StringRoute];
for j=2:n-1
StringRoute.Route='A ';%结构StringRoute的Route域依次临时存储从第一个顶点到其余顶点的最短路径
k=2;
for i=1:n-1
switch ValueRoute(j,i)
case 1
StringRoute.Route(k)='B';
k=k+1;
case 2
StringRoute.Route(k)='C';
k=k+1;
case 3
StringRoute.Route(k)='D';
k=k+1;
case 4
StringRoute.Route(k)='E';
k=k+1;
case 5
StringRoute.Route(k)='F';
k=k+1;
otherwise
continue;
end
%对于顶点数目不同并且顶点表示方式不同的图要相应修改CASE语句个数和分支语句end
StringRoute.Distance=ValueRoute(j,n);
CharRoute=[CharRoute;StringRoute];
end
fprintf('A点到其余5个顶点的最短距离和最短路径如下：\n')
for i=1:n-1
disp(CharRoute(i))
end。