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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
0 w) W" x4 P2 U% @. kfunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
+ o. w" {* E( A6 J    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
3 d) n) `* t/ I+ V! x/ d, @    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
) M. X, Y  Q1 V! ~- J3 Tend
5 C$ Y3 ~7 w2 R  X$ L, b- o: edist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
9 H0 ]( j1 S* l: Y2 a            if d(i,j)~=inf
9 E7 j6 |7 Y. d! c- J% @/ T+ O                if dist(j)>dist(i)+d(i,j)
' @4 M4 H# M- Y" Z  T" }* @& O                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
            end
' ]" q8 q  Y* e' N' ]        end
    end
end
for i=1:n
, p; ~9 B) g% ^6 i1 a    for j=1:n
        if d(i,j)~=inf
) q: t8 N. W! A$ R            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
- W8 P% J3 x+ k& c  r9 P+ E                error('Negetive WeightCircut');
( A% }/ \7 E: g3 ?6 q: u            end
        end
    end
6 E- ?" Q3 g; j0 o+ z4 lend
: C! F4 Q+ g/ L2 t+ w9 l4 Bdist
( }" I( L# m; g' E) n# Apre
4 \3 o, k: L+ Z& Eend
%%%%%%%
; f6 v7 @; M3 ~  T  ~运行如下代码：
1 {7 r* l0 r8 iclc;clear
) Z+ W! D/ @. Nw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
2 U# X' a0 l, f5 b5 J! K% {      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
8 g' d1 S' l  j. i' }3 Q      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;

! E* W# g+ ~# E/ Y1 ^5 l: YBellman_Ford(w,m,i)
3 G) h- m" a8 ^, k6 X8 X  ?. y5 ^" a%%%%%%%
所得结果：

% S8 D4 j! {0 B' `. B2 Y
dist =


     0    -2     1     3    -1     2     5     8
7 ~- [. H, ?1 w! v/ s
, @3 \" K2 h. G7 l; `
3 E. }! h8 P" b
& J9 b! O7 i. i
7 o# U2 {  e/ K2 k( q/ cpre =


   NaN     1     1     6     2     5     4     5
+ w, t5 e1 m5 L; E9 ~. l/ O
+ C8 R) D7 E3 u2 i+ W. B
5 Y$ Z' y. T! _5 ~5 ?3 f# q

9 Y1 a" {8 a8 j6 q结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！