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
* Q; g5 N5 w; M    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
, c) t- L2 ~# t5 a9 ?6 Fend
9 j; [" R7 b  |7 p: F0 ]dist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
& o+ ~  O1 \- h  X/ t                    dist(j)=dist(i)+d(i,j);
; F) N. f7 N+ h3 T                    pre(j)=i;
                end
- v$ _$ Q8 O6 O8 z3 b            end
) q0 L! S& @. i. I        end
5 R5 ~- @1 D0 c3 E2 _  T    end
end
( ?. d1 W1 y4 O) D5 jfor i=1:n
. ^( x& i2 u' ^1 \5 \! F    for j=1:n
1 ~1 P( |, ?6 h0 K5 ]        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
, n$ A( [3 \8 X0 f. S1 a8 L                error('Negetive WeightCircut');
            end
        end
$ G0 c, X( z4 d- A/ J  q$ b7 ^$ t    end
! u# u, G# T9 h4 o, M  C5 W& jend
; B; c+ }, T/ P7 z6 t' U. Rdist
+ N6 p, Y. u# w5 _, T0 i  kpre
end
%%%%%%%
运行如下代码：
clc;clear
w=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
: {: A$ s% W, |! S1 ^      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( W; x9 Y6 N& X, V7 L      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
- K$ C" q, I2 s- C5 Ii=1;m=8;
: R% b$ e. y8 E, R6 P
3 ]# ?3 ~5 a! xBellman_Ford(w,m,i)
%%%%%%%
所得结果：


dist =
6 m' ^8 G8 p  p7 e

     0    -2     1     3    -1     2     5     8
  I5 H/ w! x" C) L/ d


6 g& j, n/ A% ?; Y5 d
pre =


+ y4 c9 A- ~% V/ v   NaN     1     1     6     2     5     4     5



8 K$ H9 j- U. V9 O
3 K$ I0 X8 s# o9 I9 K5 n1 w" K) A结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
" a- y+ z! ]% I; R+ A代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！