图论算法及Matlab程序代码.doc

图论算法及Matlab程序代码.doc图论算法及其MATLAB程序代码
求赋权图G = (V, E , F )中任意两点间的最短路的 Warshall-Floyd算法：
设A = (aij爪n为赋权图G = (V, E , F )的矩阵，当v*j € E时內=F (vm),否则取an =0, aj
=+ 8 (i工j ), dij表示从Vi到Vj点的距离，rj表示从v到Vj点的最短路中一个点的编号
, j, dij = aij, rij = j. k = ②
更新 dij, i, j,若 dik + dk j<dj,则令 dj = dik + dk j, rij = k,转向③.
终止判断•若dii< 0,则存在一条含有顶点 vi的负回路，终止；或者k = n终止；否则
令k = k + 1,转向②.
最短路线可由rij得到.
例1求图6-4中任意两点间的最短路
g
图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 表示8
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 %程序结束
Kruskal 避圈法：将图 G 中的边按权数从小到大逐条考察 , 按不构成圈的原则加入到 T 中( 若有选择时 , 不同的选择可能会导致最后生成树的权数不同 ), 直到 q (T ) = p (G ) - 1 为
止，即T的边数=G的顶点数-1为止.
Kruskal
避圈法的
MATLAB
程序代码如下
n=8;A=[0
2
8
1
0
0
0
0
2
0
6
0
1
0
0
0
8
6
0
7
5
1
2
0
1
0
7
0
0
0
9
0
0
1
5
0
0
3
0
8
0
0
1
0
3
0
4
6
0
0
2
9
0
4
0
3
0
0
0
0
8
6
3
0];
k=1; % 记录 A 中不同正数的个数
for(i=1:n-1) for (j=i+1:n) %此循环是查找 A 中所有不同的正数
if(A(i，j)>0)x(k)=A(i，j); % 数组 x 记录 A 中不同的正数
kk=1; %临时变量
for(s=1:k-1) if(x(k)==x(s))kk=0; break ;end;end %排除相同的正数 k=k+kk; end ;end ;end
k=k-1 % 显示 A 中所有不同正数的个数
for(i=1:k-1) for (j=i+1:k) %将 x 中不同的正数从小到大排序
if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx; end ;end ;end
T(n，n)=0; % 将矩阵 T 中所有的元素赋值为 0 q=0; %记录加入到树 T 中的边数 for(s=1:k) if(q==n) break;end % 获得最小生成树 T， 算法终止
for (i=1:n-1) for(j=i+1:n) if (A(i，j)==x(s))T(i，j)=x(s);T(j，i)=x(s); %加入边到树 T 中
TT=T; %临时记录 T
while (1)pd=1; %砍掉 TT 中