图论算法及其 MATLAB 程序代码
求赋权图 G = (V, E , F )中任意两点间的最短路的 Warshall-Floyd 算法:
设 A = (a
ij
)
n×n
为赋权图 G = (V, E , F )的矩阵, 当 v
i
v
j
∈E 时 a
ij
= F (v
i
v
j
), 否则取 a
ii
=0, a
ij
= +∞(i≠j ), d
ij
表示从 v
i
到 v
j
点的距离, r
ij
表示从 v
i
到 v
j
点的最短路中一个点的编号.
① 赋初值. 对所有 i, j, d
ij
= a
ij
, r
ij
= j. k = 1. 转向②
② 更新 d
ij
, r
ij
. 对所有 i, j, 若 d
ik
+ d
k j
<d
ij
, 则令 d
ij
= d
ik
+ d
k j
, r
ij
= k, 转向③.
③ 终止判断. 若 d
ii
<0, 则存在一条含有顶点 v
i
的负回路, 终止; 或者 k = n 终止; 否则
令 k = k + 1, 转向②.
最短路线可由 r
ij
得到.
例 1 求图 6-4 中任意两点间的最短路.
解:用 Warshall-Floyd 算法, MATLAB 程序代码如下:
n=8;A=[0 2 8 1 Inf Inf Inf Inf
2 0 6 Inf 1 Inf Inf Inf
8 6 0 7 5 1 2 Inf
1 Inf 7 0 Inf Inf 9 Inf
Inf 1 5 Inf 0 3 Inf 8
Inf Inf 1 Inf 3 0 4 6
Inf Inf 2 9 Inf 4 0 3
Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞
D=A; %赋初值
for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值
for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)<D(i,j))D(i,j)=D(i,k)+D(k,j); %更新 dij
R(i,j)=k;end;end;end %更新 rij
k %显示迭代步数
D %显示每步迭代后的路长
R %显示每步迭代后的路径
pd=0;for i=1:n %含有负权时
if(D(i,i)<0)pd=1;break;end;end %存在一条含有顶点 vi 的负回路
if(pd)break;end %存在一条负回路, 终止程序
end %程序结束
图 6-4
评论2