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)
( {& Z9 a9 H7 t* A! a+ P%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
- }' V9 O! H6 C; o" Pfor i=1:n %初始化dist，pre
" x. v* v: H2 w" r: @    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
# t) V2 `! g& T/ {! [4 y    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
7 z3 W$ y! {0 \/ ufor k=1:n-1
* V) W8 l! h1 s# a    for i=1:n %松弛操作
/ b2 S/ T! r  h. g$ d; H& `        for j=1:n
5 Y5 V; B! |: |! Q6 E) N# t            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
- A3 u& N' x+ q                    dist(j)=dist(i)+d(i,j);
6 C: ]5 M7 b) W0 C. V7 i) D& l0 y                    pre(j)=i;
                end
            end
        end
    end
end
# Z4 s4 J, h# k) M4 Z; i  W: Efor i=1:n
    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
0 E8 Q9 S3 e/ C: e* t# H$ Z+ s                error('Negetive WeightCircut');
            end
$ [2 o: k5 y6 U; t* \- O8 A7 J        end
    end
end
5 D9 n/ t3 Q" O% z" _dist
8 C: G) ]8 }1 |! h# i0 [" [. ]7 G' _pre
- [8 z) k5 t9 q) e0 ]$ T9 pend
%%%%%%%
运行如下代码：
& I& z2 m. M: M" D  N8 H0 kclc;clear
. H3 \1 Y8 b; R+ k9 M; A4 ow=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
) [4 Q2 g" |5 d      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
; A- M9 [! W8 i+ b      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
6 I- o# N3 {6 g# Z6 L6 oi=1;m=8;
, B( n, t: g, m' s
Bellman_Ford(w,m,i)
6 ?* ?$ y! J% _%%%%%%%
所得结果：
" |' O# @3 ]& D; ~/ u- m6 q0 s' E

1 x6 P% V. m2 M. o, X4 \dist =
' |$ H! m' S( m8 `8 v

* P6 h9 x4 t% o4 u3 |     0    -2     1     3    -1     2     5     8

4 h0 w) p4 X, o9 a$ X5 E- ]


4 q4 d1 n& x& n# |' `( cpre =


   NaN     1     1     6     2     5     4     5

3 X, Y% n; m/ N
" f, [3 b4 c) N* o2 o- A
1 W+ \  M4 a- l. ^
8 c6 V) g' l6 _- b6 u$ Y结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
$ ^( p, C$ z/ z. i/ g代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！