Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
. Z5 A; M; I- Q# _, j                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
3 e7 I6 t+ h: X4 O  ]1 I                         40    20    10    0    10    25
  {/ a# d9 k) ?2 l( D# y  k                         25    inf    20    10    0    55
                        10    25    inf    25    55    0

    弗洛伊德算法:
程序如下：
clear;
2 C  j1 p5 |; ?1 ~5 S- K9 Yclc;
  C. w% ^# {" z/ }M=10000;
a(1,:)=[0,50,M,40,25,10];
) n2 k1 k1 M; W* Ha(2,:)=[zeros(1,2),15,20,M,25];
4 Q0 m( c% v' E/ la(3,:)=[zeros(1,3),10,20,M];
7 h$ K, o# Q( |8 y8 |a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
" ], o( s' l* y* h% Ab=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;
6 G2 b7 ^' {. Z6 _& Q* C+ s5 j         end
; F* r0 c) O) m      end
   end
" d( i; k& I0 M9 m- U& {( oend
  K( C! Y6 h) w/ ~b, path                  
9 _1 g! p8 z! K+ i  @% Y% i6 V3 M运行结果：
b =

& V: Q; M" L) O' h     0    35    45    35    25    10
    35     0    15    20    30    25
4 g7 `  u$ R) F    45    15     0    10    20    35
9 Y! P+ S4 F% T7 \5 d    35    20    10     0    10    25
0 G0 q9 g1 [2 N( {/ c    25    30    20    10     0    35
" }+ E7 w( Q& x    10    25    35    25    35     0
- h! y) c; t  @
+ T/ E' T# y" W% Q4 _  ~
path =
! f* F* }, l/ ~/ |& }/ }
     0     6     5     5     0     0
1 k- ~; J# W! J: f) x. s" T& D     6     0     0     0     4     0
* \, w/ N1 ]5 j1 j* L9 O2 a     5     0     0     0     0     4
2 q5 j/ e5 q  g! u2 S3 t2 x0 ^     5     0     0     0     0     0
     0     4     0     0     0     1
& G5 A6 f. i1 {5 B0 x3 V% F     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。