Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
! b& |6 E6 W' [- [4 Z" S0 \                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
                         25    inf    20    10    0    55
/ I  W2 m- I+ C                        10    25    inf    25    55    0

7 [; I+ W" U& i9 T3 e0 y& I& q+ |    弗洛伊德算法:
5 g* z- O# C1 t8 j0 n7 k1 E* Z程序如下：
clear;
, L$ {8 H2 k: {8 q) ?' Vclc;
* ?2 ~5 Z/ N$ U4 S/ b2 fM=10000;
a(1,:)=[0,50,M,40,25,10];
% {: [- L! J0 Za(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
; A8 `" n1 {) j: w) Ta(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
4 G) r$ w4 i' O6 A. ua(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
( o* l+ _" T7 `1 t4 u( ]8 c. a) _for k=1:6
   for i=1:6
# l& [" a: ?4 x6 F5 F; A      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
/ R: l6 f2 P. [# b            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
* \$ M: a6 o1 V         end
      end
   end
end
b, path                  
运行结果：
b =
( v; a. H; @6 v2 i8 Q! Z0 {# x
) g# {% V) u2 N4 W- r     0    35    45    35    25    10
    35     0    15    20    30    25
! Y8 v& u- `0 w5 w5 _" g    45    15     0    10    20    35
    35    20    10     0    10    25
    25    30    20    10     0    35
    10    25    35    25    35     0
! `$ A5 l' U! I* Z
8 q' J+ C  [9 f0 w/ `1 t
path =

     0     6     5     5     0     0
7 M! E$ p& r9 W7 u* D+ S8 ]7 U0 \, ~     6     0     0     0     4     0
2 U/ k9 Q7 |  i0 N9 ]$ ~/ ~     5     0     0     0     0     4
     5     0     0     0     0     0
     0     4     0     0     0     1
     0     0     4     0     1     0
& _' i# S; A1 |3 [& [0 v对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。