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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
4 f$ B' N0 [9 A, {& h! C" Y* vfunction Bellman_Ford(d,n,s)
$ k5 z, q0 m) Y- I, T0 o7 L* P%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
" A3 ^5 @9 G( bfor i=1:n %初始化dist，pre
8 X/ S# W1 {; E; ~( A. h    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
- U' d# T: }/ G& _; h7 _0 Q+ ]dist(s)=0;
for k=1:n-1
( Y5 c3 R; t# E# B/ k    for i=1:n %松弛操作
        for j=1:n
+ k/ y! z- S4 Z* W2 ?1 O$ C9 T            if d(i,j)~=inf
3 ]0 h) \4 F/ c5 M5 X                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
* q- b- Y' M' A" V& l9 q: e  K                end
            end
        end
    end
end
; W& P% i' L, V2 `- P5 x0 s' ^+ pfor i=1:n
    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
; J5 M% Q) S, A' X0 F                error('Negetive WeightCircut');
, ~# c% J- w' a$ [( K            end
% A( t# Q4 s  z& z' _  v        end
1 N/ b% [) P$ ~5 b4 }7 x3 t  F    end
6 t  L8 \+ `! n4 T& Qend
dist
/ L, {' R; r8 o! q  R; d$ npre
end
%%%%%%%
# d& u) o' [9 {运行如下代码：
1 v* d* g: f* `: h5 dclc;clear
" r0 Y$ @* K7 ]/ qw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
$ r" i3 I, @3 h6 T. c      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
9 `# _( Q: M; S0 a1 V      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
$ P$ ?( c9 q! W  N2 b5 }% di=1;m=8;
# c* [& V! F: |$ K7 c6 N  l& `
! z  F( L$ T; \4 s9 w- ~/ w* B# PBellman_Ford(w,m,i)
# w) H8 U6 v) l5 T4 Y6 n( U%%%%%%%
所得结果：


dist =

" I  t6 Z1 S& K7 u1 ]
& l, }& m9 j& y5 g( c     0    -2     1     3    -1     2     5     8
7 f- j, i5 |  W  a& f
# d  g9 T0 x9 u) ]" Y, Y

& P# }" h8 C/ M0 \; E
& W1 b/ f; p  E4 h. i/ vpre =


% m- E0 n# O- C/ }, w: l2 _) i2 F   NaN     1     1     6     2     5     4     5
! J3 P7 e. `" N
& O0 m" F# G7 d# O+ O# J9 t


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

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！