Bellman-Ford（贝尔曼-福特算法）算法

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
9 N. c' _  @( _( X4 o: b: Xfunction Bellman_Ford(d,n,s)
# s) C+ O; Z' Z" R. X9 R) t%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
' x& J% ^( t( ?: t: \! ?for i=1:n %初始化dist，pre
5 h$ ?; P7 o6 W& G) ^& [% o) e  `- c! v9 d    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
# n+ _& ]6 G1 w2 h0 D; k) b- |    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
" [. w9 w0 d, A' v" ]; |8 Dend
; D& _% ~# @" q# Fdist(s)=0;
for k=1:n-1
2 [) C7 P7 y; n( J1 y) k' `, K, y    for i=1:n %松弛操作
4 ^& _) N. i7 ]$ I4 L7 r        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
5 q' P( {, R4 W& G1 F                    pre(j)=i;
                end
            end
        end
    end
3 D! h! o$ l; ~- I% U# F0 jend
for i=1:n
    for j=1:n
8 @" k& g; N2 _% S: l9 T/ s        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
8 Q5 |5 W" Z! M, l2 Q: R, W  H                error('Negetive WeightCircut');
            end
8 G$ Y* V! ?; a) j$ `0 C+ }        end
    end
; U5 g: `: D' K; p, b0 E" Nend
dist
pre
end
%%%%%%%
运行如下代码：
clc;clear
$ Q- k& D/ O+ g" Y- Q5 N% o' @* e( Vw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
6 \6 P- X2 m, J8 |      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
3 Q; C4 a  M: A- v) gi=1;m=8;
8 o/ O2 ~, [* G- x0 u- E' r6 }
Bellman_Ford(w,m,i)
%%%%%%%
所得结果：

7 U  z; N4 N% k- i) U& u+ x
dist =


     0    -2     1     3    -1     2     5     8
+ i, n, [/ Q; n2 y) ]8 ]


# i- S3 {$ v: @- X$ W& J4 B  O
: X! \/ P* ~7 d' Q1 Hpre =
: h- ^$ x8 V& S/ h1 B* M
; d+ y8 W" J4 k
   NaN     1     1     6     2     5     4     5


! H4 F2 \1 T5 J
- M- z$ f- v: V  c, d
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
; x7 R* _+ b# y2 o代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！