Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
; c3 H$ [& D3 Z4 J    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
  y: T* A6 R% \5 q- Q0 q8 d' E                         50    0    15    20    inf    25
/ {0 I+ x( a7 W( p                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
                         25    inf    20    10    0    55
1 u% k8 ^# v% g7 V' a! q                        10    25    inf    25    55    0
( e) Q4 K# D$ Y# z$ t- M
7 Q* s1 h1 `" U3 Y    弗洛伊德算法:
程序如下：
9 z. L) X' L! S* |) K. @9 b+ @clear;
0 h" K$ U/ `% \) {" U' e) {( Kclc;
* ]% e! b& @9 E: p4 G4 V' F  YM=10000;
a(1,:)=[0,50,M,40,25,10];
% A$ @* U3 j! W! Da(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
1 L6 N8 Q+ \7 w: p0 V# Ca(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
2 w: N7 ~3 q8 K/ a1 t5 L4 [9 u" Ia(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
$ Q/ L3 C3 c0 Y$ ofor k=1:6
3 O& z: O1 ~. q   for i=1:6
      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
7 |# O3 X+ |5 _6 y5 Q         end
      end
   end
7 R2 M, Q2 W) `5 [4 F' X( }( Bend
& X. ]# p" I9 x1 v. n$ v# V7 U. k) s2 zb, path                  
4 y2 C! m! c+ D7 c5 }运行结果：
8 g7 Q" ?' ^3 Y/ A- Eb =
8 n! M* w5 {9 O
  @  ?; A. l/ n- z  |- T# p     0    35    45    35    25    10
& q# N) O* v! R5 g) C/ E    35     0    15    20    30    25
    45    15     0    10    20    35
& h4 ~) Y5 `" _$ C7 Q2 n    35    20    10     0    10    25
+ I8 F/ t/ y* h+ [6 Q3 v    25    30    20    10     0    35
% k' S1 N: J/ B. q2 u" D: b3 W. L    10    25    35    25    35     0
  {! J" F0 F+ C) o3 g
$ ~/ M5 Z' \1 L4 L/ v1 ^6 x
path =
' S" }% Q! `4 d1 d* @# d
     0     6     5     5     0     0
9 Q" K6 T  i) W  k5 U% D3 x% `& ~     6     0     0     0     4     0
' h& `6 c+ C4 O6 |, m     5     0     0     0     0     4
     5     0     0     0     0     0
% w& J1 t, f/ q2 b- b+ ~     0     4     0     0     0     1
     0     0     4     0     1     0
; ^+ F' A2 I- e$ y& @对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。