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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
& l! f* Y( W0 P- j( afunction Bellman_Ford(d,n,s)
0 D8 }3 D$ `  A( ^%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
) O) |8 W) z; f3 E6 P    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
( u% j2 o" j2 J; N9 r$ u/ ~    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
8 s" \; w+ e$ h" A+ m; T/ iend
- E  y' q, Y- K" p6 G& T4 Wdist(s)=0;
5 W! }6 }- V. r9 O5 tfor k=1:n-1
    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;
                end
            end
        end
5 V! a  ?% T7 |    end
% y4 q! m7 w+ A7 D) M  v/ d, _end
7 ?( l' y: o  Hfor i=1:n
9 }- x2 i( @1 b" T* S& j0 O    for j=1:n
        if d(i,j)~=inf
8 r% p5 V1 N5 C# y; j$ `            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
        end
) U& f1 i" @# \! a' e2 |& `& f! x    end
! M$ A: n! |4 send
( K! m$ u0 h4 [$ X- a( tdist
9 y5 J3 d3 c1 p2 u) ppre
end
%%%%%%%
运行如下代码：
clc;clear
0 [) Q6 q9 z) O0 B! n) ]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;...
: x. q4 T" ~, `; }# O      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]
( a( U  _' m# I" A, T4 f" |2 oi=1;m=8;

) @( g: B0 T3 J3 O4 eBellman_Ford(w,m,i)
) c. j; l4 t1 _, C0 v%%%%%%%
所得结果：

' @" I/ ?& ^/ j+ _2 B( d% w
+ o+ Y0 V( ^% ~. z2 s. \dist =
2 U$ P, i: [, P5 B2 `6 n
$ Z6 s( O8 M( n& g, h+ y
     0    -2     1     3    -1     2     5     8
' n" q& A0 |- H" ^) t8 X- s& B9 l
5 x# r6 ^  z# n! R$ x* `( }
5 H  Z( B3 M# C7 L) W6 U' B$ P: y
1 M3 p' a/ e; ]* k, \1 G6 e
pre =


   NaN     1     1     6     2     5     4     5
, N- ^( U' A1 S/ O8 E; h
& l8 I. Y- D# U, n/ |3 |, M

9 d7 }& e: a& q( s
$ m% V3 T8 @7 _( k! ?0 @; T# l) R结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！