Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
' `# ?- P: T: V3 D. _- F# E" `: }    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
2 l4 `9 B8 }) ^9 U: w0 @9 Z  {                         inf    15    0    10    20    inf
+ A: n" e6 [2 F4 G                         40    20    10    0    10    25
                         25    inf    20    10    0    55
                        10    25    inf    25    55    0

, {) z/ c, \/ y3 z    弗洛伊德算法:
程序如下：
3 \% }7 m2 t/ C  v1 Vclear;
clc;
7 Y5 Y1 u7 D7 }8 Q; e) g& z% xM=10000;
4 y4 f1 l% \( t: l) g( G+ Wa(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
$ C$ d; M" A0 ]a(5,:)=[zeros(1,5),55];
2 ?% j. _- P, ^, ka(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
: u4 k$ j. \4 `* u( n8 A. c2 Tfor k=1:6
   for i=1:6
      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
, T" u1 c/ g- X2 S7 C            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
         end
      end
! |+ y* c. j4 U$ d$ W   end
, _1 J" M% v7 x! lend
b, path                  
运行结果：
b =
% O1 Q( W7 K3 w9 O$ L- }3 Q
2 i( A5 N' M8 r4 s     0    35    45    35    25    10
( ^% Y8 M  c1 n: t) N8 {    35     0    15    20    30    25
" D& e, \2 g; S5 F    45    15     0    10    20    35
* H9 A1 R1 |) h! J    35    20    10     0    10    25
    25    30    20    10     0    35
* u7 s$ j0 S8 Q3 w$ d! N    10    25    35    25    35     0
% f6 ~& \& S+ I. b0 Y3 ]( M0 D

  B3 p8 o5 e$ h/ O: Y% Opath =
3 R0 @3 E' ?( [
/ C5 d# v0 O; S) t     0     6     5     5     0     0
     6     0     0     0     4     0
2 v" t5 ?3 A8 a# o* W. T     5     0     0     0     0     4
     5     0     0     0     0     0
     0     4     0     0     0     1
     0     0     4     0     1     0
& D$ d9 ?! r% Q  X2 q7 {对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。

7 J, V$ e# }$ @# r