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)
9 o* d% \0 z# z- P* a%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
, k- ?+ v3 {  `) d. Q. U+ C8 T) y; `    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
. r, n5 D3 f. s- P- edist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
8 V2 ~/ J" {% E: F2 w, L# ~  ~& @        for j=1:n
6 b2 X  t- B) y9 S$ M2 }. k            if d(i,j)~=inf
8 E; e) H/ _9 j: A                if dist(j)>dist(i)+d(i,j)
: h# Q) F( y4 H3 @- r' v                    dist(j)=dist(i)+d(i,j);
5 u6 G# ~, T- W- W; F$ K                    pre(j)=i;
' T) M$ e: e% {7 y$ d$ j: i                end
& N' s: x9 E5 f# j! v; i( z            end
8 p' I7 S. Q& g- O        end
8 m2 K$ R" u0 ^0 V1 G( `/ a, J    end
end
  e" m6 L+ j' X0 N6 d! a4 r4 g1 Vfor i=1:n
    for j=1:n
0 x, q! y. `5 t( [( b9 q        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
" W4 B1 P( Z" @0 q; F        end
    end
end
$ h  @) N8 z/ ~* s6 h" e, Z: X7 Sdist
. X) T* V# R9 [1 j4 upre
$ O4 J- F) b1 O; I! r( Mend
%%%%%%%
运行如下代码：
$ {- V/ {8 C) wclc;clear
1 Q, x/ R& |' G* b! t' cw=[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;...
      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;

1 K" w5 Y8 T+ T: {Bellman_Ford(w,m,i)
%%%%%%%
所得结果：

& u" I( p: P, _' o/ k6 F- p
dist =
' D7 q/ }0 z" L3 R. @. c7 @

     0    -2     1     3    -1     2     5     8

3 w3 S' O! w+ }8 c0 w


pre =
! S8 G. ]: w4 R& v$ _: q# u) m

   NaN     1     1     6     2     5     4     5
! `; D/ p) P' e

6 m) C# K) U) G( r

3 u8 p8 F! h& Q$ e7 z6 c结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
- M. R4 g3 J6 V5 u  ]4 T5 F4 s代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！