Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
5 e2 h+ }3 A5 X- `+ ~  L                         0    50    inf    40    25    10
# N( u9 B, o$ I0 N( g/ I                         50    0    15    20    inf    25
$ r9 k$ j6 C: R/ B6 X                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
, P" {9 f* S5 c* {                         25    inf    20    10    0    55
                        10    25    inf    25    55    0
. y# M; y6 V3 H* L  h
    弗洛伊德算法:
3 m6 \+ G* Q7 g9 _# I程序如下：
: d. Q5 z% ?4 p0 ]9 W5 W) Bclear;
& [5 v- i6 C" i$ R2 g9 Aclc;
7 Q! p9 V: y) {5 u, L8 qM=10000;
- @& |! x4 Z4 i3 g) T6 ~a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
; e$ k* Z; W. u7 la(4,:)=[zeros(1,4),10,25];
  u" `& x# N$ a- k+ b2 }a(5,:)=[zeros(1,5),55];
- o" ?  ?% ^7 i# Q: D, q8 Xa(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
( ~, v2 X0 y5 Q2 K) xfor k=1:6
   for i=1:6
. p" X5 W7 O  X$ v. |3 N6 s      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
5 r( p6 O. U3 ]! A" Q) I            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
' Y8 w2 Y& b5 U- K* z0 b' [! X) Z         end
* i: D1 D, G+ Y      end
( W9 y, O4 o. Y% w   end
3 Z) M9 [8 `1 `2 @6 ?end
b, path                  
( b  f* b" E5 F; b) \: C+ h. |运行结果：
b =
- m! t2 h7 d: t1 Q6 R6 s
: K% L* S8 w/ O4 c" q; f- q6 N     0    35    45    35    25    10
    35     0    15    20    30    25
8 o- @! D% F) ~/ C1 V    45    15     0    10    20    35
+ S2 z! W( m: e. w! V0 u% T    35    20    10     0    10    25
6 i) J% V8 t7 S. T/ R9 N8 j    25    30    20    10     0    35
6 R" P, e5 A$ ~$ h: q2 y8 x" I    10    25    35    25    35     0


2 T9 _$ A: s- t9 dpath =

     0     6     5     5     0     0
     6     0     0     0     4     0
' u3 L9 [9 c/ ^/ v7 F( ]9 I5 `     5     0     0     0     0     4
/ m1 f# w+ E' R6 |7 U0 G+ {     5     0     0     0     0     0
     0     4     0     0     0     1
7 k3 r: A7 K6 A/ X, g     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。