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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
% r. l/ c& a2 ]( t" Y0 v8 hfunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
, i: k! B+ M8 H  e$ [1 k  yfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
$ H+ }% R7 C# g% P2 l        for j=1:n
0 ~/ |4 V, L5 d, v$ [; T            if d(i,j)~=inf
6 f: a' D& ?0 ^- R                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
4 D0 K; c0 q: i2 I5 ~2 @9 y                end
/ k' }! f/ [$ _% O            end
* d4 [1 |0 c* p$ Y% D; L        end
    end
end
# J4 {. L) U4 H- g$ s7 Dfor i=1:n
    for j=1:n
        if d(i,j)~=inf
2 G# y2 C+ s4 X) F) S5 J            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
* L& [5 N) W$ Z                error('Negetive WeightCircut');
5 l$ b& S3 V% u            end
        end
  Z& v6 y( c9 {3 C& f1 F    end
7 ]' J4 a$ E9 \5 X: @end
: Q1 I" f4 }& F9 A0 ndist
; @/ `5 r3 }: G& R7 v$ _pre
end
/ W% _: A- p  P* H%%%%%%%
, u2 r2 Q7 m- r- s0 G运行如下代码：
1 n* I2 ]) f# J4 iclc;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;...
% P# N# c) J% g4 |- D7 `, |8 Q+ [' q      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
& Z' Y5 ]) u: x& v) S      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;
3 E& o1 K" y# A+ Y7 F6 _
* g' ?0 Q6 _: P& I% k- aBellman_Ford(w,m,i)
7 d; w% o% }1 X%%%%%%%
所得结果：
- o3 q% v: G; z3 `' W3 U9 E
+ @) _( Y$ n) B
% R  z; q, L: Tdist =
& _1 @( J  L8 r, L
; R- w4 ]/ N0 v/ O: l+ }* E0 M& Z3 o4 u
     0    -2     1     3    -1     2     5     8


: j: L; ]: H' f/ V- q
* c3 c. R% `& k( \) Z* l  i
: U3 @6 ^1 W3 q1 @pre =
/ I% b; Y% i, o5 @" u

$ f7 B3 X# I/ X' f6 y+ p" W! V6 V" l   NaN     1     1     6     2     5     4     5
/ w& E, o0 ~0 D* X: F3 @
  U, A) K! Q# ?$ l' P


) g* s& T% c  |, |; L结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！