Bellman-Ford（贝尔曼-福特算法）算法

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
# C2 r% i- k2 B* B6 R* afunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
) Q' }9 d! s1 C$ ]9 b: _$ afor i=1:n %初始化dist，pre
7 X1 Q" @3 O; C* v    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
6 q; d* _6 ]2 _end
dist(s)=0;
3 }1 {, {+ R, z- o' A3 Dfor k=1:n-1
8 T4 }  _: ?* ~6 |# X( f% s- w4 a8 G    for i=1:n %松弛操作
        for j=1:n
! p3 h( X! N6 C7 C            if d(i,j)~=inf
- y" N$ k- V6 x4 R                if dist(j)>dist(i)+d(i,j)
$ [; G( l3 n0 H/ o8 w5 a- y                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
            end
        end
% b* o8 @. ~: ^5 ~) q: U9 @; a    end
end
' Z" g! x8 [8 I" f8 tfor i=1:n
    for j=1:n
        if d(i,j)~=inf
- O. B$ Y- u  @* \! P6 c            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
7 a$ Q" o) _% c; W! [            end
        end
! P# h0 A& T" N+ Q2 M" h5 |    end
5 G  K/ g# R# Vend
dist
pre
5 j+ J6 v' j% u" D% Q' Bend
%%%%%%%
0 c% p' J4 b: w) o1 B- Y: u运行如下代码：
  B4 w. k, h' \" lclc;clear
w=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
" m; D, l2 [3 b, G      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;

* a- J3 ^$ r/ N: x9 E" ~Bellman_Ford(w,m,i)
%%%%%%%
所得结果：
. Y8 C" S+ o: z( r/ r
5 K: r4 X+ b, z+ s
dist =


     0    -2     1     3    -1     2     5     8
* x0 x1 B2 p6 l: e" O) B# _! c
" j8 Y6 b: ?" ]- \( j. H* Q

1 l+ S2 {( j# ~
pre =
- w' C/ b% B- z# n: O( ?$ s$ G
) V$ P' g: H5 n. @, o* d
   NaN     1     1     6     2     5     4     5

  D% s( M+ V2 R5 o
% e+ q8 C9 h3 q2 k8 s( l
/ _' o0 T. B2 M9 k
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

我还以为是写好的东西，拿出来分享呢

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！