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)
6 s9 u9 t; @$ L2 U. @; b%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
( c- ?7 a7 |3 F# A: G    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
1 e( X9 Q4 t  x7 X) w* d! O    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
, |% [& W1 M1 B' z; Ydist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
1 P3 M2 \; V8 R$ d! |        for j=1:n
            if d(i,j)~=inf
) F: v0 o% K+ n4 r                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
. q. x# W% v8 K/ W& o                    pre(j)=i;
) B2 k4 F* \" @4 {/ Z                end
            end
        end
    end
2 O  ]5 M. o0 oend
5 \, W! ]) ^2 R  efor i=1:n
    for j=1:n
+ Q7 s3 d, [& H/ Y        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
/ ~1 {. k' E2 z; z+ b1 ~8 E                error('Negetive WeightCircut');
            end
8 \- y' X5 o+ L9 {% Y        end
* `  f( C# ?  C4 H. l+ z    end
end
6 M6 d5 Z- F3 M- F+ L2 e& b8 Bdist
pre
& \8 L) f+ s% b  O: H7 E( \) t2 cend
+ h. o9 z' I5 A; W" W; @%%%%%%%
运行如下代码：
7 \) P1 `3 h. U6 D2 L; }( n! v8 N& jclc;clear
. c" w& O+ j# p% o7 |9 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;...
      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
) r+ i* l4 V8 J, u1 V# ]& t$ T1 w      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
( O) W' v; h4 \& _i=1;m=8;

Bellman_Ford(w,m,i)
2 p5 {9 |. C% R$ D( ~9 H5 d%%%%%%%
( S6 h: [& q  [5 g" O% J所得结果：
! N, I5 [$ ^9 N' D# g( g

; k4 }: f" Q, E$ S7 A; Q1 \% Adist =
4 b+ b8 q  ]# S6 G9 _4 ?: ?6 ^
$ ]7 g3 H: t" i6 [0 q# y1 T* [8 P
     0    -2     1     3    -1     2     5     8


0 [/ v. ^0 S' a: L; \; q# i! S

pre =


# I' z. \' ~+ C: ?5 s2 U   NaN     1     1     6     2     5     4     5
% \6 s* v" T$ B0 O- N* y


* _" o; A# `/ h9 o
$ u: o  }8 `( p: W+ o: A% R结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！