Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
9 `& f8 Y  n: F) C  W                         25    inf    20    10    0    55
                        10    25    inf    25    55    0

4 }6 L. g/ c- L9 E& k, t7 t3 k5 X0 e3 t    弗洛伊德算法:
程序如下：
4 D6 D) D' w* e3 i5 {% @4 v/ cclear;
+ T0 h7 @0 ~- `6 Y. m8 Hclc;
2 F+ j7 z5 I- A9 BM=10000;
a(1,:)=[0,50,M,40,25,10];
6 P+ g6 R2 f# I3 X& xa(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
7 t5 |7 b! B" W2 ^( ya(4,:)=[zeros(1,4),10,25];
* C1 w+ \7 i& s- `3 |, r1 j' La(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
) X5 p5 i; w" ?b=a+a';path=zeros(length(b));
* T: P+ u1 u" @  \. ufor k=1:6
* B/ W, p2 O( Q* A' `1 J6 \+ w# a   for i=1:6
& {6 m, Z: V$ P0 ]5 f% E( m& R      for j=1:6
1 j& I$ ?) T8 `4 P# J4 j8 d+ b         if b(i,j)>b(i,k)+b(k,j)
7 t0 L% R. ?3 N9 u            b(i,j)=b(i,k)+b(k,j);
5 b' O6 |; a. M# v# ]            path(i,j)=k;
. k& o& Y9 O$ C, o         end
      end
   end
% G8 k8 x0 q% Z$ eend
# S7 }' M$ R0 @! }( lb, path                  
+ w5 r2 c' a8 U8 x运行结果：
b =

     0    35    45    35    25    10
' U) [7 D6 y. y' g5 h    35     0    15    20    30    25
! n& H, `9 Z3 L    45    15     0    10    20    35
    35    20    10     0    10    25
    25    30    20    10     0    35
8 b: z% W, H! u/ o% t, w+ ^) z+ m    10    25    35    25    35     0
2 i8 [2 ^3 k3 [4 u
2 [0 U7 z! ]9 I, G# D
path =

1 p) b2 A- u8 ~; Z     0     6     5     5     0     0
1 v' ?! R& z5 A0 k* D9 }* i     6     0     0     0     4     0
     5     0     0     0     0     4
     5     0     0     0     0     0
     0     4     0     0     0     1
/ o0 V8 g. i6 e; i     0     0     4     0     1     0
% F- r% g, o, i% i+ P' n对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
- G! U( `+ S5 w) j8 U