Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
- v0 ^4 N, c4 U1 n2 A% ^    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
1 j  M4 L% j, v1 q+ s+ r( ?9 V                         0    50    inf    40    25    10
& A" _# B) A8 ]. ?% }9 V! q3 O                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
' X# k& ]' }6 [) v                         40    20    10    0    10    25
  ~2 u+ {% |% F$ ]: _                         25    inf    20    10    0    55
                        10    25    inf    25    55    0
, }; ^9 I3 z3 [  `! X, Y
    弗洛伊德算法:
4 @; [5 B' w" l程序如下：
clear;
) p; A" P- i' S& xclc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
% \8 A  y, D( Xa(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
9 Q! V. N; J  `; {a(5,:)=[zeros(1,5),55];
* a( X8 B5 x; G# \9 J" a) ea(6,:)=zeros(1,6);
0 B1 q4 Z# R& d+ \- mb=a+a';path=zeros(length(b));
for k=1:6
$ ?' t& ^9 z  a" \- Q   for i=1:6
      for j=1:6
  B1 [5 ?4 ^2 K$ e         if b(i,j)>b(i,k)+b(k,j)
2 f4 P/ `! k4 R0 I. ~2 \            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
' o) O# i/ u& u# F  Y$ d         end
      end
4 u! I2 E; Q# z8 X) {4 _% q8 B   end
6 }" ?" u  r- T. }% ]) {1 Send
  |! }& r" B* b& Y( u9 Sb, path                  
' o1 Z2 E2 I0 S7 @! F7 I2 t9 S运行结果：
b =

     0    35    45    35    25    10
( c; M' B1 T+ X* I; k6 B7 o    35     0    15    20    30    25
$ Q3 c5 K) N) F, ?- e# L* Y    45    15     0    10    20    35
2 i9 R' }; f1 z% ~    35    20    10     0    10    25
    25    30    20    10     0    35
    10    25    35    25    35     0


path =
2 O3 p% M5 l$ {* J
     0     6     5     5     0     0
     6     0     0     0     4     0
: W9 @1 w$ Z% g0 ^8 u; p- @     5     0     0     0     0     4
     5     0     0     0     0     0
3 U/ z) U/ l3 b. x8 B     0     4     0     0     0     1
6 L4 o. J1 r7 J# h$ v' T     0     0     4     0     1     0
; y; L/ X' D$ e) A8 R( \对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。