Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
/ g# s7 |" u  }/ n: X4 I* M9 i    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
2 M) m/ e8 e0 g( Q2 w  Y                         40    20    10    0    10    25
                         25    inf    20    10    0    55
8 x$ `8 V6 b. |6 A  K+ Z                        10    25    inf    25    55    0

    弗洛伊德算法:
程序如下：
clear;
" n, @" [- j  U# w4 hclc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
' _- y( ^8 `. E# a. Wa(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
3 {( Y! D$ c3 h) Z5 Wa(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
: `: i5 H; {5 Pb=a+a';path=zeros(length(b));
4 E; d/ v9 R! D( G5 h; ?: ^for k=1:6
7 S1 b9 u& u- K5 f   for i=1:6
      for j=1:6
1 C# u/ r3 l  t7 K7 _! r# ^+ A+ o         if b(i,j)>b(i,k)+b(k,j)
: S- R/ f1 C% v$ Y1 J4 S            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
5 Z& N1 t3 K2 d% F% o# c/ _( Q         end
      end
   end
6 T" V- y- ]5 S2 ?) E% P+ wend
( ^$ R: ?: u6 K1 J$ m+ o1 zb, path                  
运行结果：
b =

     0    35    45    35    25    10
4 b7 M! m- Q! A2 S. ^. q* D9 Y    35     0    15    20    30    25
: O; ]; T/ `" A/ F/ @  F8 m    45    15     0    10    20    35
; J/ z* D: M1 L, Y6 ~    35    20    10     0    10    25
3 r8 s/ @1 V% ]2 }- K* Z2 c    25    30    20    10     0    35
2 _- h9 i) q; c1 l/ o    10    25    35    25    35     0
. O2 |  Y+ n6 M

path =
4 C8 {& b+ O8 n2 @' Y
2 M! p) L- S% C9 w3 _6 E' V- i     0     6     5     5     0     0
/ w; {, R' m' L  R, V     6     0     0     0     4     0
- p1 @' C' C9 |  |7 e6 |& L     5     0     0     0     0     4
     5     0     0     0     0     0
3 D" ?  e. `( l4 E1 F+ H; `. o     0     4     0     0     0     1
$ j# c, m, i/ \" C3 k  C1 E" N     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
  j* H* I9 Y( J1 J9 `) w1 `0 _  V