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)
  V# H6 t( f$ L3 b$ k& b%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
+ M' C0 e! }8 S3 r7 Z/ P8 _) [    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
, L7 I! N% L) R# Z" [end
& K& Y+ v; u0 h; Q- D( Tdist(s)=0;
3 c! T. N( I  ?( r2 L" p' c5 Pfor k=1:n-1
) J5 n8 n; C% D" u$ y    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
! L9 p0 D" r- G  Q- l                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
            end
8 d8 s$ t( H  ^+ H; ]$ g. X        end
4 V9 u( J* w+ L8 v# N7 c7 I    end
end
! ~) K# B  W; {+ t0 {for i=1:n
    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
" q6 {- M: l4 b* Q                error('Negetive WeightCircut');
            end
  f8 c% m  {2 o6 l# D; b        end
+ [8 u! z% G& C- H% |/ Q/ z    end
end
! a8 Y! D2 E6 H4 v2 ^dist
pre
end
" p9 D1 ~1 n' K/ l5 Y( r%%%%%%%
运行如下代码：
3 X+ W+ |" y$ e7 O& ^9 J2 G8 tclc;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;...
$ j* J2 F; {, J' \# R* f. i4 R      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]
' m* r- _  n) mi=1;m=8;

1 N, X9 P1 r; \6 I: FBellman_Ford(w,m,i)
%%%%%%%
9 z. i9 ^6 M* ^; n2 D: ]所得结果：


dist =

8 n% L6 v0 _# K, o! d
     0    -2     1     3    -1     2     5     8

) N, O2 q- V* c; m; l8 I4 d
3 u% g* x0 F" E9 k
" s5 R# Q  @, k8 J4 B
pre =
' N; B+ \; Z8 g0 j) W/ |5 I
- T+ o4 \* m& o: T/ O3 X" |% y- _& b
9 n$ @. ]- H, C3 t   NaN     1     1     6     2     5     4     5
/ i/ p# ~. x& i- N3 V2 t" ^



结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！