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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
function Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
7 k. K+ A# ~7 K0 M# `  afor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
; D: ^; E2 {8 r4 d9 `for k=1:n-1
& L9 H0 y* Y. J; W/ M( ~% ?    for i=1:n %松弛操作
        for j=1:n
2 O; q/ Q. D& e+ g; D! d            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
+ V/ `- i" ^) l3 j3 a" h* P                end
# a1 e# F+ X+ Z: e0 A0 }            end
        end
    end
end
for i=1:n
    for j=1:n
; {  a8 ~; X6 @0 C& R" O        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
9 X* k+ l' I  H; \" }( s& {7 f4 g2 @            end
& m) `+ \) N4 t; _# e( t        end
) T! W) {* P, s0 U  V8 s1 }' R0 R    end
end
: p, Q& Q; d3 m+ ^( a" fdist
# V, a+ W3 _$ k; Z3 Q9 |4 p( gpre
end
4 D* @2 }1 k6 k) W( Q%%%%%%%
运行如下代码：
% f3 ]4 }9 a- L# Y( F4 aclc;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;...
) U' X: z! j% E7 Q" b# U. b5 Z      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)
%%%%%%%
: B; r+ F( T! d所得结果：
) M2 e  M) @. d5 I

dist =
( l, Y& ]  p$ S
, q  q) m! t8 O
; `  h. K5 Q+ ?0 F* L/ h2 i0 L- S& `     0    -2     1     3    -1     2     5     8
' B7 e( |/ i/ X. h( H



- H) @. }% M: h$ y$ ]pre =
3 O" u8 F% l; c
8 {+ ~7 A" B- n! T; H( G( L
   NaN     1     1     6     2     5     4     5

# Q" o/ u) h& t5 h* W/ L; _6 G0 R
& _$ S  a. H  N: s2 S0 `
9 L; N  R/ B# {
# e) b9 B" P! o+ o- U- ^结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010