Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
7 D) ~) P0 ?6 M5 |0 @9 t/ x                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
+ W) `1 N) C: d) l% g8 g                         inf    15    0    10    20    inf
. \% ]8 ~  S' T: v) i6 M# r                         40    20    10    0    10    25
                         25    inf    20    10    0    55
                        10    25    inf    25    55    0

    弗洛伊德算法:
* ?& B* }# T; l程序如下：
clear;
clc;
. n- g8 [6 _% H6 RM=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
- t5 G" a% W2 `, w* a7 g# va(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
1 x4 [. ]0 @9 Aa(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
1 j1 T# W" m6 S' m: @b=a+a';path=zeros(length(b));
for k=1:6
3 b  h- E# t: H. c. i6 E' ?6 ?   for i=1:6
% k% P, T4 ]# j: F! F4 z      for j=1:6
2 u* x4 [3 x5 m- y& {. T         if b(i,j)>b(i,k)+b(k,j)
, _6 u, Y  _, K            b(i,j)=b(i,k)+b(k,j);
. \8 t; o& [* w* E$ Q6 O! d            path(i,j)=k;
, i: V9 o& D& @6 c5 M9 j         end
6 P5 d+ x3 z* J$ @6 b5 u      end
   end
2 B8 k7 i& ]( Z6 g. oend
b, path                  
& c: X; O  `4 x2 `5 a运行结果：
  U* s% k1 X& L5 ~b =
( M- \$ j' `% P# Z* H; Y( G
     0    35    45    35    25    10
    35     0    15    20    30    25
    45    15     0    10    20    35
    35    20    10     0    10    25
    25    30    20    10     0    35
* ~4 i" U# W+ n+ B9 Y    10    25    35    25    35     0
9 ~0 D( D* X' F$ S5 K- [! v) I

path =
  m; A. [) s/ H/ T4 K' M
     0     6     5     5     0     0
5 Q4 q1 t3 Y4 G     6     0     0     0     4     0
     5     0     0     0     0     4
     5     0     0     0     0     0
. ?' X* R6 L3 m' Z3 G     0     4     0     0     0     1
; h% j" I9 |' ~     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。