Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
5 d; p) Y( G7 X$ K                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
. X0 ?/ A* _# k4 T3 u# G                         40    20    10    0    10    25
                         25    inf    20    10    0    55
$ F' M/ ?7 T' H. |- j                        10    25    inf    25    55    0

- a. p" L0 J$ `6 O    弗洛伊德算法:
/ p6 W& L/ i. [! _2 A7 U6 z程序如下：
2 i. a4 k' E& X' P$ pclear;
& o+ m8 z) \& z/ w+ gclc;
& n5 w/ S0 |: EM=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
  d5 m4 v! m3 Wa(5,:)=[zeros(1,5),55];
- L; M! w# R! C% xa(6,:)=zeros(1,6);
/ r+ F* y- p: n/ v8 E! Kb=a+a';path=zeros(length(b));
for k=1:6
   for i=1:6
5 V0 g0 m3 d, y+ Z: s& n      for j=1:6
2 P+ w% w5 u# W6 Y, a         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
2 M8 v+ A3 \5 D: w  C; @0 G            path(i,j)=k;
+ \2 j9 o$ |! \* u. r( R5 w- f( x         end
      end
1 [: Y! `1 E: A5 j# e   end
  F4 X# k* W; A% ]( uend
b, path                  
运行结果：
, B6 a* |2 J8 ?; |+ ?) j0 \, j) R  [b =
( p' k" L6 l1 s6 o8 |
/ a( T. B9 x7 l9 c- ^: x+ s     0    35    45    35    25    10
    35     0    15    20    30    25
    45    15     0    10    20    35
, @" `; q9 Q5 m1 X' O    35    20    10     0    10    25
) ]6 L/ f. L) y/ I3 l! o    25    30    20    10     0    35
    10    25    35    25    35     0
5 l' C4 |  N5 ]4 P7 u% ^% b2 h! {

path =

" V; d" v1 W9 V* y     0     6     5     5     0     0
     6     0     0     0     4     0
     5     0     0     0     0     4
     5     0     0     0     0     0
$ u3 S- y$ F* y% q% P( L! j% J     0     4     0     0     0     1
     0     0     4     0     1     0
4 C) C8 q7 u/ C6 `对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。