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)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
7 E. ?- C4 ^" Q* y9 g        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
" E/ B+ b3 h& }; l# L) }" e                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
+ ?/ e9 b4 j" r" Z" P) P                end
) F% o+ C+ I0 f1 E+ c            end
        end
" U1 U9 m3 x0 ?& \: q    end
+ d6 e. F9 j: tend
for i=1:n
    for j=1:n
# U2 z/ e' {, p5 i        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
! j# a# L) s; _, ]  G; K  x        end
    end
6 u1 _( j% I, ^  M- G6 F, [: hend
/ J/ D$ c6 P5 j: t% [dist
& |, \/ s2 L6 qpre
end
%%%%%%%
3 b4 a9 t& P9 ^运行如下代码：
% Y% R6 T* \+ J! E0 gclc;clear
% g3 W  H6 L$ I- Q3 uw=[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;...
' r5 u  m) K! ^% j      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;
" L+ v# Z" H6 Y, u
Bellman_Ford(w,m,i)
" B- [( r6 |; Q%%%%%%%
2 D* }6 F' D0 C4 ]' Q所得结果：


4 ?8 h1 I/ ~2 J" C4 c7 ]" rdist =

% u& N( ]% T2 P( ?$ D4 [3 o
4 l: ~: `9 Q( T6 u( K6 O3 a9 O     0    -2     1     3    -1     2     5     8



5 {1 T) {% q- e' ~3 l
pre =
! Z1 Y, U# _3 v. `. D
( T* a9 E, V9 U4 w3 R% V
   NaN     1     1     6     2     5     4     5

$ h1 Y$ g6 ~; B
0 j- N2 \6 L; j& a0 S/ e
1 ^9 `0 F; b& U( }, ~& L
% j, C- q9 m/ ~$ s3 X. L结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！