Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
6 R4 h; f$ X( X' L3 k: z    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
8 J+ B; i0 V) O                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
                         25    inf    20    10    0    55
& j! e% h7 x' M- W. e" |) Q! E; b                        10    25    inf    25    55    0
' q( E9 `, l- b+ Q; O( j2 I
    弗洛伊德算法:
程序如下：
' F' T' ?6 g8 N0 K4 pclear;
7 |) C( T9 Q+ {$ j9 C4 U0 o* Nclc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
3 F8 Q# N, c. m4 g" Ca(2,:)=[zeros(1,2),15,20,M,25];
3 K3 M$ K  O0 w! I& m; va(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);
4 u0 ~3 t3 Z1 M1 Pb=a+a';path=zeros(length(b));
for k=1:6
( F& ~) C' K( j   for i=1:6
  D3 Z6 ~$ z6 ?" {      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
% @  {8 Q1 a  x. T            b(i,j)=b(i,k)+b(k,j);
) Y# G9 R) q* d. S( p            path(i,j)=k;
# }) I/ f8 N) M# y* M9 a         end
      end
   end
- I: T# ?7 C+ D6 l- v" |4 N3 b: hend
b, path                  
2 r% g. ?1 E) R# c/ g运行结果：
b =

     0    35    45    35    25    10
$ E5 C7 V( M7 A; f    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
* s  ^; B4 [- d! `% Y3 `
% n% ?3 Y4 c( L! m" X8 N
path =

     0     6     5     5     0     0
     6     0     0     0     4     0
! t2 b9 K' x$ A     5     0     0     0     0     4
" |/ _- N4 g, Z9 i8 |1 ~% \& z0 j     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。