Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
' F$ U1 j6 z8 e" }8 R5 _3 |    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
; O0 @9 Y0 t- m8 f0 N: t6 z                         0    50    inf    40    25    10
9 L* x! x6 o) S+ P% F6 Y" _                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
# V" X. o4 D- H! S9 s                         40    20    10    0    10    25
                         25    inf    20    10    0    55
                        10    25    inf    25    55    0
8 X: c, i9 S" p0 @6 t# p0 g
' B' c0 g: R! x+ `8 Z    弗洛伊德算法:
程序如下：
clear;
clc;
% o: _+ {# u4 h: }0 t0 T. KM=10000;
6 A: A: |3 i$ q' u2 A1 l9 Ha(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
( z/ I+ F4 s/ ]2 z5 pa(4,:)=[zeros(1,4),10,25];
2 T$ A( l4 o( v1 O7 d$ D3 q" Xa(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
" T1 K1 w/ C7 F$ s* Gb=a+a';path=zeros(length(b));
for k=1:6
   for i=1:6
/ y! B, R7 l+ o7 Q. p. r      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;
         end
9 s$ [! }2 j* H/ p$ P: b8 w" ~      end
   end
. |$ _8 i9 ~# b5 Q" Oend
3 a5 e) p& h! v# sb, path                  
' E5 }5 u# t: @; D5 k2 |运行结果：
! v7 `* n& A8 Q6 K8 N: |b =
+ M' j* n: f% j0 |( _/ `
     0    35    45    35    25    10
0 J5 n$ d$ W, ~8 ~" ^, q3 @0 X3 c7 y    35     0    15    20    30    25
# D( g' L3 @: T0 Q2 ?" j% k$ t$ t    45    15     0    10    20    35
: c+ n( y/ z- D    35    20    10     0    10    25
4 r8 x- |& U, Z5 J/ J! z( T8 L6 o! h    25    30    20    10     0    35
$ w; Z7 Y2 Y& [1 [" Y# K    10    25    35    25    35     0
, x; X8 ]6 S* I: E) _% ?

path =
& V) o' R" [# T) ]( j; m, Y
     0     6     5     5     0     0
9 @, |* ^4 F1 }- U7 n     6     0     0     0     4     0
     5     0     0     0     0     4
& y7 d& x, I  t4 C9 N, q$ J$ }5 L     5     0     0     0     0     0
     0     4     0     0     0     1
" z% ~% h( v7 C. N" b  g     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
" A2 b+ h5 i( o! h3 i
# D& ^3 V; A; x( }