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之间的最短路的长度
, V% D! J6 k5 V' k2 w6 E& s" k    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
. b! |1 J- T/ m3 \- Y+ q" cfor k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
! x! ?0 x3 F( `- ^+ u            if d(i,j)~=inf
3 e4 k, K- ?# ^( q0 U+ g9 d: H' _                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
) J/ Q/ \! G6 H* K) h9 c0 v# Y4 |                    pre(j)=i;
% x5 I: C5 k9 A* a& @' B                end
! o" X) f! G$ r. e' K2 r            end
        end
2 @$ c9 o8 ]# k; m/ t- ?2 x    end
' W$ o0 l+ t. f$ x- x6 Rend
4 s* W$ j2 ^5 f: Tfor i=1:n
  g3 I/ x+ y# j7 {; m    for j=1:n
( q$ k0 m1 F% l4 \9 B9 Q. c# ?        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
5 x7 \! b7 f& c5 g5 ]            end
        end
2 {1 n  p0 u" u3 n    end
end
. c" t% W5 m2 T" l9 w! P: i& Jdist
1 W6 G  R1 k! N' Fpre
end
%%%%%%%
: L. d0 [2 n. Q: l8 ^运行如下代码：
8 D  c" R: P4 a, }' z4 W+ tclc;clear
$ S5 V) q, Q6 o/ h0 b+ p9 a) _4 y) Jw=[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 q9 R9 t' {' A* W, s& L+ o      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]
i=1;m=8;
% r& t  ]7 s) X
Bellman_Ford(w,m,i)
%%%%%%%
所得结果：
" }: m+ w2 K5 O  N) y* F, x2 P$ r

dist =

7 s+ s  W3 Z7 Q+ o1 G9 k
     0    -2     1     3    -1     2     5     8



* g+ @" _! l# K' M* p) X& D
pre =


   NaN     1     1     6     2     5     4     5

: i9 Z. b- o! z( T; @
+ T3 Q0 n, {; r0 }6 \4 g' n

$ V0 i" B) j4 x& W6 c结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
( Z: I: w1 O/ S, J% k4 }1 Z8 v/ ?代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010