Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
3 F2 [  V4 ~6 A2 I4 q% J                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
                         25    inf    20    10    0    55
3 O. b: B2 z# n/ s' X: Y  t. R; A                        10    25    inf    25    55    0

    弗洛伊德算法:
, Z. C3 V  x/ m1 W) M) H程序如下：
% f. W" C/ q" r, M7 Jclear;
9 x! C- O, r1 ?9 O/ X5 Iclc;
$ P3 F* q, \! @; }1 xM=10000;
$ Y% B2 z5 z5 A' I  X! va(1,:)=[0,50,M,40,25,10];
3 H7 v+ R! r% [' v1 i" E; }. K% T4 t8 ~a(2,:)=[zeros(1,2),15,20,M,25];
/ P7 ?, Q' I: o2 H$ E: A. Z2 z7 va(3,:)=[zeros(1,3),10,20,M];
! H$ Y3 k% b6 v) ga(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
for k=1:6
4 n3 C& u9 `( n* P8 Z  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;
' s$ ~8 s3 q7 t! Q5 R         end
2 X, f2 r# p( q9 l% I+ w: b- V: d1 y' z      end
' _  |, A" u: N% c1 \   end
end
b, path                  
  U' b* g& I1 R. D运行结果：
b =

, Q. I; r& C+ o  B9 f. e- o     0    35    45    35    25    10
- k" N' R) b! H, O7 ^    35     0    15    20    30    25
0 R  y7 `5 _+ M7 i" Z( a, A    45    15     0    10    20    35
8 U( v, {4 h. B" |# V2 B    35    20    10     0    10    25
    25    30    20    10     0    35
    10    25    35    25    35     0

: M; f5 ?7 a6 D9 w2 d
path =
/ D1 r& k5 P7 V! g
     0     6     5     5     0     0
. U/ Z1 ^9 R1 D7 K  r7 b5 D     6     0     0     0     4     0
     5     0     0     0     0     4
     5     0     0     0     0     0
2 D: _) X- N% c     0     4     0     0     0     1
     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。