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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
1 {+ v" p& l  \1 M; ^function Bellman_Ford(d,n,s)
, e3 g- t9 n2 t%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
( S* S) x4 g# w, s& o/ Ifor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
6 b- j3 K* }- S6 o; t( @end
  s! c8 a, x4 @0 @. Qdist(s)=0;
for 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)
  y, g; q  b! i" n1 w                    dist(j)=dist(i)+d(i,j);
: y# G( p" d/ l# A, Q3 p                    pre(j)=i;
$ v8 A6 I6 q# T+ K- O1 ?$ x! p/ n                end
            end
        end
8 a2 t& ]- U1 B; Y8 W/ R    end
( B1 L$ q- ]. l7 Yend
6 N4 ?$ s% D' y4 f6 |; Qfor i=1:n
7 f: h  a$ W) z( _) F; T) w8 e    for j=1:n
3 h+ b6 J/ }: i2 d$ _' o        if d(i,j)~=inf
& v2 X- `0 T/ q# v. q3 k' ^5 S            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
        end
    end
end
dist
. W2 W- `1 Q) c, s4 }  fpre
5 I) v0 i( M; {end
& n& L( A% {; s5 P- Z%%%%%%%
$ ^3 H1 v/ Q9 |" O; D运行如下代码：
- }1 ?4 [, Z1 t; jclc;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;...
7 V, Q, k( ?9 p6 g+ k2 B      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;
, `: h7 H! k1 A, E0 T% |) S3 L
" X) C% _2 B; c! \( |9 @Bellman_Ford(w,m,i)
%%%%%%%
1 _5 [4 N- x8 ^! }( h1 u所得结果：
; A/ j7 l* `, j+ J! c2 T/ A
! a: ]9 g% ]. j9 b+ S" B! N
dist =
6 f! s! Q! r( g" x9 o/ _
. s  `7 }8 T7 w! C
( j" d. K& j' m. X     0    -2     1     3    -1     2     5     8
3 B6 s$ a1 Q6 |+ M$ u
! ~# g; `/ ?- ?9 Y


( \- E1 n8 ?5 a% n5 ]pre =
9 ?& q  W" p% C$ W8 @2 f, ^
) l) K1 F$ y7 R# [, a8 u3 h) V# ^
   NaN     1     1     6     2     5     4     5
+ J" @# W- q+ ]4 u


: q$ D) N, R5 f- ^
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
! H  s) x; L) J; E代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！