Page 213 - 数学建模算法与应用

第八章 图与网络模型及方法应用

最后，当 k=n 时， An 即是各顶点之间的最短通路值。
例 12 用 Floyd 算法求解例 9。
矩阵 path 用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd 算

法的 Matlab 程序如下：
clear；clc；
n=6； a=zeros(n)；
a(1，2)=50；a(1，4)=40；a(1，5)=25；a(1，6)=10；

a(2，3)=15；a(2，4)=20；a(2，6)=25； a(3，4)=10；a(3，5)=20；
a(4，5)=10；a(4，6)=25； a(5，6)=55；
a=a+a’； M=max(max(a))*n^2； %M 为充分大的正实数

a=a+((a==0)-eye(n))*M；
path=zeros(n)；
for k=1：n
for i=1：n
for j=1：n
if a(i，j)>a(i，k)+a(k，j)

a(i，j)=a(i，k)+a(k，j)；
path(i，j)=k；
end

end
end
end
a， path

我们使用 LINGO9.0 编写的 FLOYD 算法如下：
model：
sets：

nodes/c1..c6/；
link(nodes，nodes)：w，path； !path 标志最短路径上走过的顶点；
endsets
data：

203