Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
+ l" q$ F. n0 R' E8 T    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
* P; @* y- P! i1 T: s                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
                         25    inf    20    10    0    55
                        10    25    inf    25    55    0
! m% U& ^  w' ?. Y, l4 X
* ~" g( `; x+ @2 Z* v& `5 q    弗洛伊德算法:
程序如下：
' }2 K, |/ ^6 X; ?% Fclear;
  j$ S# \, ?# y' }* sclc;
. e( H  K7 n0 c" F7 o, g+ CM=10000;
a(1,:)=[0,50,M,40,25,10];
& i! K  f, V) |( W- ?& H3 r' Va(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
, G# W& {5 n" |$ ^$ Wa(5,:)=[zeros(1,5),55];
* Y- I5 Q3 j: V% e6 }) va(6,:)=zeros(1,6);
" L7 u2 x/ a5 g% Y1 Qb=a+a';path=zeros(length(b));
3 [! A' i. E; d) h. ^6 G: u7 Rfor k=1:6
   for i=1:6
      for j=1:6
: y3 |5 z; _4 ^3 e         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
. @; G# s# h' A# Q4 \3 t! g* M) h            path(i,j)=k;
  R: d7 _" R( O1 O& z9 y" b6 B( O. k         end
      end
0 s. K, S( J2 o4 x   end
4 _7 ~8 X1 u( C# Z5 e9 F$ gend
6 `2 C& v/ y9 H6 k5 q8 Mb, path                  
1 l+ a* o( ]4 e: P运行结果：
b =

5 B$ J: {# @; d$ ?) g     0    35    45    35    25    10
    35     0    15    20    30    25
* ^. L9 R( g: u1 r" x- M    45    15     0    10    20    35
    35    20    10     0    10    25
    25    30    20    10     0    35
# K# q# H# ^% @  C4 l8 H( y    10    25    35    25    35     0
" P  s& M, O* e1 ~
5 N$ N: P( |7 o; X9 U% A
path =
7 @; j* O4 i. B1 I" u& D
- |1 B8 U& ~( a4 A     0     6     5     5     0     0
% N; \  z3 h# n+ G     6     0     0     0     4     0
% V6 A: o$ X* X     5     0     0     0     0     4
( f/ g" d, `4 u! p     5     0     0     0     0     0
5 H! T% B# g) C" i% ~! q     0     4     0     0     0     1
0 z, s% X, a- P3 z) ]1 S     0     0     4     0     1     0
0 d4 j! H* S9 d  O! I对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
6 p& Y1 r9 S+ \0 p/ d  }9 N