Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
6 V6 L! a8 }; k1 l/ @: Y! P: k, W                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
4 @5 C7 L6 z# j  u( p; _                         25    inf    20    10    0    55
                        10    25    inf    25    55    0
# @$ w# s/ ^5 j7 o/ F
  R/ x0 Y$ Z" O    弗洛伊德算法:
9 f8 I' q) _. E9 P程序如下：
& {) I# j9 H( c- _5 cclear;
0 d2 O0 ?$ m3 V* cclc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
2 O# W$ D6 @  r' Ya(2,:)=[zeros(1,2),15,20,M,25];
4 V# Y8 X* B; t& Q; W, k1 I: g! pa(3,:)=[zeros(1,3),10,20,M];
0 m/ V; Q( y+ e! ua(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
8 }5 V4 M5 i- ?* y6 Vb=a+a';path=zeros(length(b));
for k=1:6
7 o0 _4 ^/ b& t8 r( ]   for i=1:6
/ x3 D; R% \+ K& s# x# E      for j=1:6
: _3 ~2 F* X% s5 @7 r5 f$ w9 v         if b(i,j)>b(i,k)+b(k,j)
9 Y0 {3 S: b* J4 b3 i            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
         end
      end
   end
end
& s1 t' @# f) C0 L$ bb, path                  
1 Z+ s) Y7 f6 y运行结果：
b =
/ s' X  L. d; a$ |$ L  U
     0    35    45    35    25    10
    35     0    15    20    30    25
3 ?' n/ v2 b6 ~  e2 u# e    45    15     0    10    20    35
$ b6 _! K! k" M6 U1 T& W    35    20    10     0    10    25
, \4 O  K. ~8 Q. n* V* ?    25    30    20    10     0    35
    10    25    35    25    35     0


  G- I- P" j* m4 b; L$ lpath =

* \7 Z' B! z4 q( i$ s     0     6     5     5     0     0
' \  @5 a% j) J2 w* I5 R- N     6     0     0     0     4     0
     5     0     0     0     0     4
     5     0     0     0     0     0
     0     4     0     0     0     1
6 _; O0 _6 n$ V! P     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。