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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
" Y  k) `( i. c$ ]- }( Bfunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
2 B& [( O% ]5 x  _" p4 bfor i=1:n %初始化dist，pre
* p. o- v$ _6 ?! i/ Y    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
6 t0 c4 F3 D) a0 Q3 h    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
+ y9 W8 ^% x: Q1 X: T8 Eend
# z0 K* X5 ?7 A+ r1 pdist(s)=0;
for k=1:n-1
$ O/ N6 v# m9 N, u3 z( D    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
' d! ^) Q, j& |4 r                end
            end
: B5 T$ G4 C. D7 w        end
    end
, H  i7 i' d# eend
  R) o6 J' y2 H. ]2 D* `for i=1:n
3 a5 ~* E0 _, \3 o$ z, a    for j=1:n
        if d(i,j)~=inf
6 J3 E. w, q( K4 }            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
' u4 R. h& U% S! m        end
    end
end
dist
: t; a( u1 P, I$ Q- wpre
end
" q; x2 ?8 W. b3 X# z1 C) Z%%%%%%%
0 H: b% `2 H/ Z5 S& w# M运行如下代码：
1 e0 N, A1 n. d% P+ x- d" }- Cclc;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;

: |  O) _1 E7 P! pBellman_Ford(w,m,i)
- O1 o) G: [: H/ A! ]' j4 r%%%%%%%
所得结果：
3 |6 _/ W- I' Q/ M; d6 \  W

dist =
+ {( |! B0 }7 A; T  r  y# J. F

     0    -2     1     3    -1     2     5     8

% {5 ^. {8 c4 Q0 n
* ]4 E; O  y. [* j5 H, o0 H% T

' k/ z0 Z' }$ ~. ^8 \pre =
8 }4 E, V/ q, \3 f3 p+ [! ~

4 B* E  Z8 m! ^0 O   NaN     1     1     6     2     5     4     5



" U# r( _# ~, P, L9 Q$ d
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
2 M0 X( l4 k* \, g: C3 n. q代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！