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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
" l6 l% {4 K* Q) s) M5 F+ i3 Ifunction Bellman_Ford(d,n,s)
; u9 s% J4 Q- _) i4 R9 ^%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
( C( [! L0 v. W- R# }for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
& r  @3 r( i. B- H# _for k=1:n-1
    for i=1:n %松弛操作
7 C1 I- s6 V- N. g. w/ c1 R& A! h: _        for j=1:n
            if d(i,j)~=inf
. V% J6 }/ f- w! o% F  q# F                if dist(j)>dist(i)+d(i,j)
  r1 k) t7 \; ^) g- d1 ~. C                    dist(j)=dist(i)+d(i,j);
  l5 w4 `4 S# h$ z% i                    pre(j)=i;
- @  V5 [* E2 c2 k4 W                end
            end
8 o/ z: l+ q3 G+ j% \1 O# l7 I. v        end
. J( ?) `, N% |4 c  x/ H    end
4 o- I* Z2 v. T/ z# _end
for i=1:n
    for j=1:n
        if d(i,j)~=inf
3 f# |9 H( k/ _0 x" F# z7 e            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
) {- d0 x8 u: o9 h/ g' B8 {  d        end
* l& {, E( U# H5 i0 P% D5 T' T* S    end
end
! {+ Z8 ]% M3 z7 b4 pdist
8 q+ F2 ]3 h! @  h/ cpre
end
. B6 s- z& r; i3 M%%%%%%%
运行如下代码：
clc;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)
& p% V! K% D$ l%%%%%%%
所得结果：


! g* V2 R& S/ f5 y, I* L$ X3 Bdist =

, I! b, i. _) d* h
     0    -2     1     3    -1     2     5     8
6 n  p" S/ B: Q. v. j% K: k

- e0 W) G2 Y$ [2 `: i
# D% z; u; N" ], w) E6 t
pre =
* Z* c  j6 t* X9 w

   NaN     1     1     6     2     5     4     5

0 L2 e0 X& I) {" p
0 e2 J$ r1 |5 }8 x. ]
' S- B' }: v; x4 X* t8 |0 t3 E! I
% t$ H0 n4 ^6 f. L( E结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！