Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
0 l5 _) P5 D  t0 E                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
& E9 A# ?1 n" V3 T1 o' }: r                         40    20    10    0    10    25
                         25    inf    20    10    0    55
                        10    25    inf    25    55    0
5 p& _* ]2 \7 j- B+ u2 g% c3 ?
+ d+ w) H: o" K# p5 ?2 {6 }, r    弗洛伊德算法:
% v! G; c0 p7 B9 g9 F. x. ]程序如下：
' \/ l7 R* i: M0 p! p& ~7 W( W( B) Vclear;
2 f2 M: {0 ]' G, aclc;
, x) B3 p/ `8 h( bM=10000;
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];
+ E1 o0 z" ], L8 N( }a(4,:)=[zeros(1,4),10,25];
( ]8 ^* f5 X( Q- D4 F3 E3 Y+ |a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
* g4 L" U; B2 M4 T) Jb=a+a';path=zeros(length(b));
2 j, K: E6 \3 u7 m" }for k=1:6
   for i=1:6
" J0 T2 u* ]9 k; z1 o, X: a      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
" I$ T8 A8 ~- n/ q            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
. ~. {2 e5 p" X4 Z: h  O         end
      end
- g" s) w# H) z$ o0 D0 s5 ^  p   end
end
b, path                  
运行结果：
+ ?1 n( g8 Q/ h/ }6 zb =
- a$ {. k7 F/ {/ ?, A- Q9 L
     0    35    45    35    25    10
    35     0    15    20    30    25
    45    15     0    10    20    35
! B1 k( A3 D) n/ q4 b3 l2 W    35    20    10     0    10    25
    25    30    20    10     0    35
$ u+ d4 @& E% W& z, [& H/ A4 X    10    25    35    25    35     0

" M" ^& I5 q1 ]
5 ], B7 J# U1 j6 K! K0 C& ppath =
) H6 P6 C( C# p* q" j; h# _
* W$ S* }/ O( F8 X; L     0     6     5     5     0     0
: _& m! w% [. w$ \' A8 Q5 B/ f     6     0     0     0     4     0
     5     0     0     0     0     4
     5     0     0     0     0     0
     0     4     0     0     0     1
, m/ j- o& j7 c  ~& e% A     0     0     4     0     1     0
  O9 b% D  j6 ?& Y+ {) l5 O对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
5 A" s- y/ }% V" x% @( T5 R
% m! r" a/ f1 H+ \$ I