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)
4 _0 E0 J& ^* W: \3 N%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
8 D8 M+ g8 i: h& Cfor i=1:n %初始化dist，pre
3 l; c' Z2 \5 b; Y) F" r    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
) L/ V) F. D* C( u. zend
7 y) k4 L7 j& T8 D# r) }+ Edist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
# ]/ A# k% S* Y$ d' Y        for j=1:n
7 [2 c, X" Y8 C/ y; o0 k- s; R& ]            if d(i,j)~=inf
: j: o  i+ O' D3 w2 [! i                if dist(j)>dist(i)+d(i,j)
; f0 I2 b# D6 f  d3 I# e( @                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
0 m  c. Q, v4 y6 K; j            end
        end
    end
end
for i=1:n
    for j=1:n
; y* p, E# {$ m4 m2 `0 P        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
6 q. H# `. D2 h* G                error('Negetive WeightCircut');
            end
0 @$ B& N" S3 _2 H# n        end
    end
end
dist
pre
' B4 ~( V$ o! f/ L5 ^end
%%%%%%%
运行如下代码：
clc;clear
3 d% M- b5 W9 N3 L  }. _$ 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;...
      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
, Y: B4 E7 l, E  A7 P      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;
; y6 i4 z; X2 h7 x& B8 I
Bellman_Ford(w,m,i)
%%%%%%%
所得结果：


2 o! r3 w$ K" I- @; s8 Z9 f/ ^& tdist =


4 D: u' g8 t* ^' }: q: R6 B4 t' @6 D0 ~     0    -2     1     3    -1     2     5     8
' l8 i- C' a: o" W9 [9 G) |
7 U- ^+ x- m9 q# x1 R
) d) P9 Z7 E  S3 P8 m
2 J5 C- S& U) X6 g: [
/ F2 o( n! [1 Rpre =
4 F% L; P  o7 m! Z7 ^0 j" y$ {$ u

   NaN     1     1     6     2     5     4     5
( p1 d9 w/ R, v' ^
0 Q# x/ Q+ e' Y5 d

3 j4 E" Y6 ^+ @9 n8 Z) K' I* R% r8 x; ~8 n
. `0 ^2 r/ j6 o7 M结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！