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)
- k* \. N$ J  ]/ c; {%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
* |. h0 w7 f! Dfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
8 E# J: z8 o, @! f& n  W: M2 {    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
. `2 O4 R4 t2 h) m% sdist(s)=0;
for k=1:n-1
0 V  y% ~$ s% n0 S) J  S    for i=1:n %松弛操作
        for j=1:n
& j6 s4 }4 U8 I5 ~3 H            if d(i,j)~=inf
; [- x/ R. C6 ^: _; \7 Q                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
' F4 T7 a. h3 C% _  W            end
2 V" x- y. _/ I: h) r        end
- ^: a0 ~, U: }6 P% N    end
end
2 _5 V0 B6 |) q. }5 G% ^for i=1:n
+ N: ]  b0 K+ ]* _; ~    for j=1:n
& c& }; w- O/ w1 O        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
( K6 o! V8 }  c6 U$ d            end
        end
    end
end
" `9 f0 b* u. s9 T; F* ^4 k0 Udist
4 |$ l! s& E5 G" z; q3 L  U- kpre
; ?4 K0 P. m8 g8 s2 @end
%%%%%%%
) C5 L/ A( x, N; y运行如下代码：
clc;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;...
      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;
  Q7 ]! l  g4 y& s1 F, u3 d
Bellman_Ford(w,m,i)
%%%%%%%
; T# O4 {  Z2 M0 D: U所得结果：


dist =
& i% i, ?# x0 t# }7 O9 H
8 M5 H" u  q, o! z/ p, V+ @$ j
- r, r; n, V; G     0    -2     1     3    -1     2     5     8


. `- ]* K7 l5 A& W& H. F
' t4 ?( |% k$ k3 v5 {" O
pre =
3 Z' y0 s) L1 M" I4 s2 w% k1 ?

   NaN     1     1     6     2     5     4     5


3 _2 ^  ~& s; H. p: i( Y
' H7 ?! m% p- W' J( d1 p. N! i4 [0 a0 {
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
5 O4 ^1 Z1 L/ n! D; F代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！