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)
/ W! w8 p/ T# \+ ~1 j# l5 S%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
6 C1 Z! \/ q+ Z+ B* M, X* Q1 l    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
1 C/ x$ ^# S+ u* K7 Vend
6 O6 C; }. v" [dist(s)=0;
6 d) u" @# |3 v/ w/ xfor k=1:n-1
    for i=1:n %松弛操作
) H; Q8 a/ s4 Y7 T3 ~9 D        for j=1:n
            if d(i,j)~=inf
+ `4 c3 G9 ?$ y2 K8 Q                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
4 D; }! |0 Q- M3 |) J4 b                    pre(j)=i;
+ T  ~8 d5 e# u; J( u                end
* F) {7 w% e$ I6 I& {3 [$ `7 B            end
' L) I1 T9 S% m! f7 {        end
) P6 u& I. C& M    end
end
for i=1:n
    for j=1:n
5 f! l$ f6 O; N/ F2 O% Y        if d(i,j)~=inf
0 L3 T8 F: S9 s7 ?# e6 p' [) q            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
8 b' x/ {4 ^- ~( ?                error('Negetive WeightCircut');
* P% R+ }5 v% V: _; F            end
        end
9 A* Z( [6 U/ `% P, ^    end
) K) \( u# K9 eend
dist
# K6 V; S2 }& h$ g1 r, L# [7 apre
end
6 N+ E8 ^& W8 H; h3 \%%%%%%%
运行如下代码：
& R7 t  D8 U! W1 tclc;clear
* T! c6 I9 |- U  `0 a  Hw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
' L  V" t3 ?0 y8 Q( H      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;

1 V* Y2 B' X& ]: s) W% e2 y# MBellman_Ford(w,m,i)
7 P$ i: u/ d) I2 E8 ^2 E' R" T%%%%%%%
所得结果：
% d2 n2 ~9 j& n
) I: O3 u. }2 F  d1 I8 [, S
dist =
; e9 o. N7 v, R- L& m# \' p* Q

     0    -2     1     3    -1     2     5     8
2 W) C( \  y/ N0 b
8 [- f) c. B7 e* v& D3 n# w" b
; L5 B2 |! G( |' i% j
% ]  S, O8 [  l: T7 m% I, Q5 x6 N
1 O8 E% Y4 H7 q7 R+ n' ^pre =
. n5 J; \& w, m

4 J% {5 V, ]4 z8 m   NaN     1     1     6     2     5     4     5
( f5 D- e8 G/ W

$ N# ]; Y" K  [  ?* F/ p7 k
# u9 G4 j9 e! U( m$ W3 z: j# K
2 D4 S  b7 M  J& L, p5 J7 \结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
8 ^" [6 s( T) E1 z0 ]代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！