Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
% k" w) t# ]8 e8 ~3 F) ]                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
# {' [% c$ T; f& L8 r                         25    inf    20    10    0    55
$ _) s' V# |! x" m- s; j; X                        10    25    inf    25    55    0
- O# }& w- c0 @) N
( S# ]1 J% k8 R/ a5 J0 m" ~- [+ G& z    弗洛伊德算法:
程序如下：
clear;
2 w& j$ r0 U4 @+ i2 Wclc;
M=10000;
: [9 i# u3 Z% a2 @  T# z3 L' y( F5 Oa(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
, r' r: K+ o5 S6 [% t1 ga(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
for k=1:6
   for i=1:6
* `; \+ b) T3 \0 Y" o' u      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
2 i1 p* [2 S/ }. s            b(i,j)=b(i,k)+b(k,j);
0 q/ k: |5 @& e, B' p  B# l            path(i,j)=k;
         end
2 ^2 A" H% ]) @3 A6 n& ~      end
% p* `/ i% ~, B& X5 I; \% @   end
end
& f5 k* j. G, t0 ^) Z3 f7 Sb, path                  
% N; h$ K5 u" L6 p+ E5 o运行结果：
) V8 \: X+ M9 cb =

- z' }0 s' V8 O     0    35    45    35    25    10
    35     0    15    20    30    25
" e+ O- M3 O3 K0 F" m    45    15     0    10    20    35
    35    20    10     0    10    25
3 Q8 Q6 j& ]4 A- I8 w    25    30    20    10     0    35
6 M% I9 ~4 A) I3 Q' q    10    25    35    25    35     0
/ V0 y, O) ]; d7 e# }; N' O* r
3 ]9 z" ~  ]! E( p2 t
path =
( k/ t" l1 ^  C, y. v2 `) k) a& z
) t0 @) p0 b* B/ R* G. O     0     6     5     5     0     0
     6     0     0     0     4     0
5 c4 i/ Q5 ?0 a. O6 J6 H+ ^     5     0     0     0     0     4
* M+ M3 w7 b- O2 F     5     0     0     0     0     0
     0     4     0     0     0     1
     0     0     4     0     1     0
0 D, m: h5 b! E4 \  D# y# E对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。