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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
# @2 X$ u! g& b+ I& Yfunction Bellman_Ford(d,n,s)
3 `9 A+ z8 W3 g8 `& H0 n7 r%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
; X- A9 R& k* B* V- Bfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
) S6 I2 V3 ^+ j7 |& g7 Gfor k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
) b( X7 G% d/ j9 S            if d(i,j)~=inf
% ~  H8 p, R5 [3 c                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
2 D1 C1 D: G1 R            end
( w0 W2 Z0 B: g2 E        end
, s' i' d. u0 i: O# |, G0 X    end
# F/ O' T1 N% A8 B/ send
for i=1:n
  @3 u3 \/ ?  ]    for j=1:n
        if d(i,j)~=inf
' Z, L# G! h( N6 K+ l            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
        end
  F# v- a8 |2 A' ~' A  J    end
+ ~; M' A5 b+ G6 g, V9 H$ x( Z% m; jend
dist
) W) @- Q; U$ L5 H6 }! r! lpre
end
%%%%%%%
5 ~- e6 W5 c3 L+ D运行如下代码：
clc;clear
2 t! z  J7 w. `  Iw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
) c, u% S: ?3 W; ~. @3 \      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;
9 A+ t9 n* F8 W! Q' p' }
, A1 i2 C, c0 a( V; pBellman_Ford(w,m,i)
%%%%%%%
所得结果：
+ R1 @- H2 g& N9 o7 J' [

dist =

* e, ~$ N- r/ n* }' @
     0    -2     1     3    -1     2     5     8
$ c* G& H, o9 {- p& g
$ O. h5 L  G8 `5 _
0 b3 p- I5 ?& Y' ~4 d
1 y& j6 d; m1 o; q- G! k: L4 V
; ~5 k4 g% S, _& [9 m' f: vpre =
/ H5 u1 [5 |- X6 @$ D; C4 U) Y

   NaN     1     1     6     2     5     4     5

/ h& l* t6 c6 A
0 k& e1 H; ^/ ?' E
% j, D9 E" x# I6 K# D. B
  w: W+ Q$ f# A: u  h; B! t& O+ p结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010