Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
7 R2 A* |- K2 g    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
0 t6 n! c( [7 G- H* E3 D' c. F                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
" _, a  I1 Q1 W" s4 G                         inf    15    0    10    20    inf
$ b2 c9 W3 E/ N3 A6 b- I. T. c: l                         40    20    10    0    10    25
9 S( e( G# Z6 M9 L+ t, [                         25    inf    20    10    0    55
* [, p4 t) j; B  i% H* L# M                        10    25    inf    25    55    0

* A; c+ j5 z: H- R; L    弗洛伊德算法:
程序如下：
clear;
clc;
! f; |: b1 Z+ i/ P$ ~8 Y0 @* OM=10000;
8 k2 n+ ?" v4 G4 Za(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
. Y. V) D& z5 T/ _6 Aa(3,:)=[zeros(1,3),10,20,M];
) }+ r* ]! e" i; }7 g1 ?# J! L; Ca(4,:)=[zeros(1,4),10,25];
( X5 U9 g( H% Z7 l8 va(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
0 x' A0 s& o5 Mb=a+a';path=zeros(length(b));
2 _6 c! a( u* d& G4 y4 cfor k=1:6
   for i=1:6
7 g- j6 s& r* ]3 a+ X" B      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
+ k( u( g  z; A: c. p/ L            path(i,j)=k;
         end
      end
+ O) `: r$ {9 k8 r: ?. }* v   end
end
b, path                  
- K* i  j, ^8 C" H6 r7 a* _运行结果：
b =

     0    35    45    35    25    10
    35     0    15    20    30    25
) I6 ]  V* V% ~1 I/ W1 C    45    15     0    10    20    35
    35    20    10     0    10    25
. E+ j) y8 N, m5 w4 x! w% y    25    30    20    10     0    35
    10    25    35    25    35     0


* I: J! h- g! O. n2 z( Z% m1 i! }path =
7 p$ k% }! }: i# {7 w
     0     6     5     5     0     0
  B% g- g, X, K) N1 g     6     0     0     0     4     0
     5     0     0     0     0     4
7 M. G3 q6 F/ E5 Q/ `- t     5     0     0     0     0     0
     0     4     0     0     0     1
" }- t- y9 u3 G' J  h     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
; V/ h8 I6 }3 W8 v0 }: g