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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
) l% k4 A' C7 [! H9 R4 pfunction Bellman_Ford(d,n,s)
0 a7 v% b8 [4 ~9 y! Z# Y%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
5 w$ u/ f* M) g    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
. `" B) F6 b  [8 u) ~for k=1:n-1
$ A+ @* ^7 Q( @3 Y! B$ V" W  q    for i=1:n %松弛操作
1 O% x3 M5 x' P: T7 B# O        for j=1:n
5 ]+ r3 k/ G8 X  Q0 O) @            if d(i,j)~=inf
# d9 I. v: R) u. `/ ]1 r( |0 k% I                if dist(j)>dist(i)+d(i,j)
9 G3 v" c3 g+ U0 l. j# p                    dist(j)=dist(i)+d(i,j);
; @4 q1 }1 |7 K" }/ B/ O( z                    pre(j)=i;
) w5 p. Q5 |5 i6 p5 ]4 A4 N                end
6 ]) M+ t% ^/ `3 l            end
$ s& r( U- d5 O( f0 A& }        end
    end
end
7 Y% Q- D& b7 m% y" l: {5 J$ Jfor i=1:n
    for j=1:n
        if d(i,j)~=inf
6 u' x; l6 ~, R            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
        end
    end
: P- Q; k0 S" w" K$ ^5 H6 xend
& A+ }" J* T9 w! @0 l1 K# H3 C. ~/ adist
9 j, q/ m- _8 U: f# }" bpre
end
%%%%%%%
& Y2 M- G# o' D+ a8 M2 `1 B, J运行如下代码：
clc;clear
  }0 k, S2 b' rw=[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)
* H& g8 D4 [5 B" x8 l) y' J3 U%%%%%%%
2 ~; ~6 _: J7 m8 d4 u; C' b' u所得结果：

( o1 ?1 h, {% K% p8 r5 u4 I% j3 V
- a6 C  n" l$ @" e8 p0 J2 ?- fdist =

( z2 x! p6 U- _( F
     0    -2     1     3    -1     2     5     8
* L% W, h6 ]5 d5 b' Y8 U: A
: x7 Q7 x/ [9 L# L) m: M

9 N, R, `: S# I, `4 Y1 s
pre =
8 M# m# l! |2 V. z+ n

% e; ], X% [3 ^7 [   NaN     1     1     6     2     5     4     5



. i3 Q8 y& h# K+ n
/ k9 r& D" J4 w. Q# c结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！