Floryd算法求解惑

shuidishenyu

    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
4 P% d" v+ I9 h6 ~) W                         0    50    inf    40    25    10
) k) I+ P, D) |8 E9 a                         50    0    15    20    inf    25
! ]& {& d9 f' K0 X. w) Z5 e' ?                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
& r$ ?( B! a2 D  g                         25    inf    20    10    0    55
                        10    25    inf    25    55    0
$ `0 l. y6 f2 }
    弗洛伊德算法:
! X) ^; \: ^5 M% o* S; m( Q程序如下：
4 h# y$ I  A& v0 p# l8 s( vclear;
% A& q- n7 _/ _: s' E$ Y0 L" yclc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
3 ~1 A8 l9 D9 P6 P# i5 Oa(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
) R, O  B1 g" \; H# T' _- zb=a+a';path=zeros(length(b));
# D) }& @# j9 G! f- Nfor k=1:6
( ?0 Z; s5 w% E! T* {9 n. O& m   for i=1:6
# k5 j! Z$ q) h' \/ y      for j=1:6
         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
; a. Y  h+ [  _" K            path(i,j)=k;
         end
      end
+ U8 l% P% R* l$ {! `2 C5 j   end
end
# C! k  c9 r5 x0 {7 T/ ^b, path                  
运行结果：
6 k7 H( H' O& t* e+ e/ `5 ab =
$ K7 Z  Z) Y4 u1 C6 Z. h( R3 `
     0    35    45    35    25    10
    35     0    15    20    30    25
    45    15     0    10    20    35
  A2 K# T- Z4 i' j# X3 W# V    35    20    10     0    10    25
4 E& v  A0 r: f2 M+ `( t- Z3 |# y; Y    25    30    20    10     0    35
    10    25    35    25    35     0

: h! U, a7 t" N2 S# N0 t7 D
path =

8 v# k" j8 [$ t     0     6     5     5     0     0
     6     0     0     0     4     0
     5     0     0     0     0     4
+ Z/ ^) c1 F; j. ^0 O7 J: k. a  A     5     0     0     0     0     0
* t$ Z* k* n1 U     0     4     0     0     0     1
     0     0     4     0     1     0
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。

* `2 E) R7 Z$ x