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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
% a3 L4 N0 U- F* r) X/ Rfunction Bellman_Ford(d,n,s)
5 ?" z5 H; N7 h8 ]* `%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
4 E1 H  V" W2 [* w* M  `( Cend
- L; ]6 `7 M8 P2 k! F7 zdist(s)=0;
' k* R( a. R$ y; I! lfor k=1:n-1
$ |! W+ [  [7 v0 `    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
$ L  i# E9 W; d" i                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
0 S- X! q; i; t: J            end
        end
" W) p( e  w" @  v; U& g    end
end
for i=1:n
    for j=1:n
8 w1 j8 Z6 L5 g8 a4 O        if d(i,j)~=inf
6 S, m9 Q) ]( o; _& @, z- K            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
1 h; _+ [& E# R; q# L& [                error('Negetive WeightCircut');
            end
' |' o5 J% z1 T' A$ [5 @        end
    end
end
dist
pre
* Q( @  h  t1 G8 P% z9 T# }) l6 `end
1 w$ z* U/ C; G$ P%%%%%%%
% C% n3 w+ G( n" ?运行如下代码：
/ ~' B) h* s- P7 k. _$ t& Iclc;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;...
& {/ f+ e$ P3 }* j& R- Y2 E* t      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;

, @) B( p7 d* f6 g& T' zBellman_Ford(w,m,i)
8 d  T9 a# E/ N3 B- }9 u8 Z" l%%%%%%%
所得结果：


dist =
7 P/ P6 o/ d- \& M) Y: }0 J4 \
$ B# f' F5 t% z! X! z
     0    -2     1     3    -1     2     5     8
% x9 L: D" b: _- O, {



pre =
$ m  M6 p2 o! E: p
! y3 W0 R4 M+ l, _. Z- W5 U
5 s" C/ ]5 J  {9 K) _1 q0 v, Q   NaN     1     1     6     2     5     4     5
4 H2 Z" }7 ]$ b& t



. m% o' O2 c" p- \8 s5 z3 [结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010