Floryd算法求解惑
在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
0 50 inf 40 25 10
50 0 15 20 inf 25
inf 15 0 10 20 inf
40 20 10 0 10 25
25 inf 20 10 0 55
10 25 inf 25 55 0
弗洛伊德算法:
程序如下：
clear;
clc;
M=10000;
a(1,:)=;
a(2,:)=;
a(3,:)=;
a(4,:)=;
a(5,:)=;
a(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
for k=1:6
for i=1:6
for j=1:6
if b(i,j)>b(i,k)+b(k,j)
b(i,j)=b(i,k)+b(k,j);
path(i,j)=k;
end
end
end
end
b, path
运行结果：
b =
0 35 45 35 25 10
35 0 15 20 30 25
45 15 0 10 20 35
35 20 10 0 10 25
25 30 20 10 0 35
10 25 35 25 35 0
path =
0 6 5 5 0 0
6 0 0 0 4 0
5 0 0 0 0 4
5 0 0 0 0 0
0 4 0 0 0 1
0 0 4 0 1 0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
页:
[1]