Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
  \8 m( S/ {8 k! f! z                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
/ M3 q7 z4 ]& B- I                         inf    15    0    10    20    inf
8 o( d: J& e  M) k% r  J) c                         40    20    10    0    10    25
# e7 S: x3 X* B                         25    inf    20    10    0    55
                        10    25    inf    25    55    0

  L5 [. Z5 j3 ]. W; C' ^1 R    弗洛伊德算法:
程序如下：
clear;
clc;
( x! v" C( M$ S" X$ q; XM=10000;
a(1,:)=[0,50,M,40,25,10];
5 M# |; G8 O% Y0 z; t8 ja(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
- o# H2 h6 C' H8 M" g2 P1 Oa(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
8 D/ Q5 }0 v( i8 I$ l& E2 c! P8 B& {for k=1:6
   for i=1:6
+ H, Z- o: S0 X. B6 C      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
1 A$ h8 o9 Z" }+ |# U            path(i,j)=k;
         end
      end
  W2 \# Q& S! }. v) [( _2 c   end
end
b, path                  
运行结果：
b =

- _, P3 W5 }7 Q9 H     0    35    45    35    25    10
8 ]% w. P9 h4 t& j: \6 h    35     0    15    20    30    25
1 \9 S- c: J1 z, G6 @3 a    45    15     0    10    20    35
5 I2 Z0 x: [% T8 r7 W2 ?4 S    35    20    10     0    10    25
* K2 h" ^  C, O2 Q9 A9 I    25    30    20    10     0    35
5 i2 w% o( Z8 y3 A, j3 y  h    10    25    35    25    35     0

- l' M  F1 U% k
- m- }3 b! B+ I% `+ Z7 {path =

     0     6     5     5     0     0
/ I# G; [  b8 w7 J: \( c     6     0     0     0     4     0
+ j$ M* D2 N4 _7 v$ K: _- l1 r! O9 |0 e     5     0     0     0     0     4
     5     0     0     0     0     0
7 b4 n4 y0 ?; m; ^/ \     0     4     0     0     0     1
     0     0     4     0     1     0
. [4 l, n+ _8 V) a" t& [# \: W4 \" q对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
2 t0 R+ }* o, ?7 d" u. d