Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
1 q0 \( E+ y% G  i8 i' F* A    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
1 ]2 c" d0 G7 [) S" y                         0    50    inf    40    25    10
: o  C3 E" i" l& H                         50    0    15    20    inf    25
                         inf    15    0    10    20    inf
& R" |+ f  F; ~& D                         40    20    10    0    10    25
                         25    inf    20    10    0    55
# w$ l2 k2 O: ?- q. Z( J                        10    25    inf    25    55    0
6 C3 ^8 H3 t7 Q$ O
1 a" |. D8 B/ o8 Q% Q4 `! e1 D    弗洛伊德算法:
! U: D6 M, I6 H5 k) J程序如下：
clear;
clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
# C# F9 P4 }1 r  qa(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
8 x, o' Y. }! F% E, |. fa(4,:)=[zeros(1,4),10,25];
$ x- h4 x5 I3 k8 x4 |6 aa(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
  o6 Y. f; h( z/ Wb=a+a';path=zeros(length(b));
for k=1:6
3 B3 R3 O; A+ i3 w( s, {- L   for i=1:6
2 ]% @$ H+ k" U      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
2 h" @* Y6 y) K; f) ^: c            path(i,j)=k;
5 e: ~% S% Q' ]1 q4 ?& K( {         end
% k. R" P  V- j- A8 y      end
6 Z, x+ n! X6 O) [( |7 o/ z   end
end
b, path                  
3 o2 K% _+ I0 G! e运行结果：
b =

3 z2 c5 ]% `6 `% p8 e     0    35    45    35    25    10
: i1 w( e  a8 ~: Y  U& C# @    35     0    15    20    30    25
    45    15     0    10    20    35
) Z5 G1 W6 r$ b    35    20    10     0    10    25
5 A  ~9 n4 O3 H! Y6 T; E    25    30    20    10     0    35
9 N! x: `: s/ c! L) ]% n, Q    10    25    35    25    35     0
# t( _& r+ a9 f6 ]+ \+ c
, R) n, ^, r/ Z5 c9 Q1 n
path =
: h. A1 E: ?" E* Y% V" z0 u
. ?+ I% I8 F3 C& A; {/ x7 i& r     0     6     5     5     0     0
' b" p4 u2 k% x2 O6 G% f0 [$ R     6     0     0     0     4     0
+ P# u& t9 @& g) q; O     5     0     0     0     0     4
     5     0     0     0     0     0
     0     4     0     0     0     1
* i) Z  k6 C& ]     0     0     4     0     1     0
# U/ K& g5 U; s8 c7 ?. S  ?对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
' y+ `3 \6 s: s1 e8 l1 |