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为源点标号
  q  u. D3 n9 o/ G, E0 w; k$ ^: efor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
/ n4 w) ?  u6 p! n    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
* w# ~" R  E$ K* i! E* Eend
dist(s)=0;
6 f' ^/ A4 C; Z( Y2 yfor k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
. I  R: I5 m; v8 D            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
) Q+ a, `9 |6 C/ @; V6 M                    pre(j)=i;
                end
            end
        end
    end
& q& R# H/ h4 I) Y3 y/ @end
for i=1:n
" `" g/ r4 n* @( p    for j=1:n
3 Y; d4 Z# l9 m  k        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
9 L8 n& N& P- O! z  J            end
3 Z3 T  w  B8 p4 z" k        end
8 g7 B) y- X8 Q    end
end
! W* f, f" @, Mdist
pre
9 r! n5 S3 M& A% Y, d6 ^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;...
      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
. i. ?& B# T9 U  s3 h" c* A( w0 P      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
' r0 S# _' A. p+ O% m- fi=1;m=8;
5 U: [. h/ S* s& c+ B9 c7 [' z' \2 X, a
. ?" ?' l2 w$ h  m# s$ [" A7 hBellman_Ford(w,m,i)
) p0 C. Q5 J; N%%%%%%%
. S3 F  \6 `9 n% b所得结果：
$ T* S* i% }9 K* F' S
  h: M1 m2 I- G0 `& M/ F/ c0 y
dist =
" \" T7 [, ]1 D. D% K
. ]7 T9 s# c0 _& f
: A! [, V, l; d  p  s" p( R     0    -2     1     3    -1     2     5     8
+ R5 H0 h8 {8 x: h- L, P% D
& R" \4 [# v4 t
, Q& x' D# p( ^5 ^

# o9 `8 N2 n% I0 u' Tpre =

7 O: h. r* G  v, `
   NaN     1     1     6     2     5     4     5
: i0 k: H& s1 R3 _) v7 t7 x4 W* P

- i8 t1 R- A2 s9 w6 B
2 }/ Y& b! M+ X9 X: c; M
( S9 Z$ p0 u  U9 f6 y6 z结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
* {; e4 r9 \2 C代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010