Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
4 Y8 k* m5 o0 j6 V    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
3 [1 \2 f- _0 k1 ~. |                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
+ W( j) E$ }) o0 A                         40    20    10    0    10    25
                         25    inf    20    10    0    55
                        10    25    inf    25    55    0

$ r# a# A# L& G    弗洛伊德算法:
5 k- W9 y$ @) z- `- V! C程序如下：
clear;
: b) s/ a6 C/ Y5 Dclc;
M=10000;
0 a6 \( @' @9 P  t0 `7 Wa(1,:)=[0,50,M,40,25,10];
2 L% C* c: C/ Ma(2,:)=[zeros(1,2),15,20,M,25];
a(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);
/ _9 g9 D/ M' S  N' i/ u9 Gb=a+a';path=zeros(length(b));
/ K  C9 `. y, N2 Sfor k=1:6
' p0 m* |! }' _8 o1 m; @2 j1 n6 H% }   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;
         end
& J( o+ s5 ~/ U/ F      end
   end
end
: {5 z7 a* r: c; p( bb, path                  
运行结果：
b =
, i0 P3 I9 k) I% d' Q2 U
- J( e0 u  I1 E7 J6 W6 `' h. \     0    35    45    35    25    10
    35     0    15    20    30    25
1 k8 |6 K% V4 Z) Y3 j5 |$ i' _    45    15     0    10    20    35
1 v3 P  u& @3 O7 n    35    20    10     0    10    25
$ E& k6 @& @* Q, i: N' h: M    25    30    20    10     0    35
    10    25    35    25    35     0
* Q& B% c9 s5 {1 O
' P6 t  q( d, j6 D* V. E
- [2 M& E& z# S, a  ~3 y2 Opath =

     0     6     5     5     0     0
$ K# G; n% P# {  d/ [     6     0     0     0     4     0
     5     0     0     0     0     4
     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。