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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
9 y0 b/ j' O6 C' E+ A, g) c0 xfunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
- h" y, E, w" \3 V( D3 Dfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
  D/ z% j% O# P* J    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
4 }5 y8 s; _( k( s& Hdist(s)=0;
# i3 w- _$ \* I5 f, _  Zfor k=1:n-1
. E, b, H8 x2 ?4 ?7 x    for i=1:n %松弛操作
; p* j/ Z; Z& a- d        for j=1:n
# Z4 {2 v! L/ k% a* G            if d(i,j)~=inf
4 d. D8 k) T, t  ~. Q0 p                if dist(j)>dist(i)+d(i,j)
+ l" K& H' Y9 c) z# \                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
: ^4 f1 H2 _' Z7 n8 x/ q7 j                end
3 q2 r! R2 g+ f5 k            end
        end
2 F! \. Y5 q  c- ~. l  o    end
6 E: U! y4 t8 Y6 B& v2 e8 W/ Eend
$ i, [6 r8 R( ^4 a1 e% Mfor i=1:n
' @/ Z6 D$ I$ B( \) V9 L    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
& I, G! S, I# P( ?! w2 m( C            end
( \5 f0 K$ z, ~8 m/ ]/ m        end
3 S. o$ j' Y8 a) \* q3 ]: p    end
end
4 B" Y. ^+ q. j2 @! t2 xdist
pre
end
%%%%%%%
: G0 ^5 e" o- p+ C运行如下代码：
2 ]6 f/ {1 c! g% t( m7 e. sclc;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;...
      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;

Bellman_Ford(w,m,i)
%%%%%%%
# E/ _) O" [  S% M1 w. O, i所得结果：
3 w# C: v% O; |8 i" A8 @) f1 S  i( {
$ V+ r# O6 `" U1 k) A
dist =
, h: |0 ^8 {0 t) ^! A

( A; k8 _+ @, g8 U7 ~( I  q# {     0    -2     1     3    -1     2     5     8
2 x- D1 i4 t! a
2 _( [- Z/ z8 n6 T/ M" H& W/ T
% W+ o4 H2 A, I+ z$ x

pre =
" S: a: q( h+ j! g1 L! F
! M- ~8 A  a/ I0 W# y. U
   NaN     1     1     6     2     5     4     5
: [9 f, o# b# Q! M2 V% I& J" |' g

, Y, ]" w! j# n# ]' j/ `

. C2 ?+ x( I; H& C! x3 S1 f结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
, t1 G  V% a9 g- c代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！