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)
# R' Z- n" V3 i$ C% p. U+ [%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的前一个顶点
end
0 f8 _9 ]3 Q  R+ C3 Qdist(s)=0;
3 u) o$ F' f# Y/ r$ u) W: Afor k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
) p! y( J' a; a3 x: b                end
; U! {5 }2 I* i* o; ^- i            end
        end
    end
8 ~- F& q+ l: Gend
for i=1:n
) ?; n( D2 p8 B' e/ \    for j=1:n
: ~# K6 x$ n1 d' J# D        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
. G9 b; C$ p8 l) N. G                error('Negetive WeightCircut');
            end
0 I$ F8 d+ ^) a( k: W        end
1 ?1 t. ~+ @: ^! N0 k    end
: u6 F  W, n. ?, ?, Zend
dist
1 Y6 S" e+ T5 }pre
+ l" e: X9 T; {0 Jend
%%%%%%%
9 P3 R4 r9 x- l! p! i' c运行如下代码：
& G3 `6 m+ a+ C  u8 Xclc;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;...
5 \1 R( d# a. e) I      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;

7 R: c) v; P+ |) YBellman_Ford(w,m,i)
9 W( [8 D0 R4 G( c; h0 x%%%%%%%
) q0 Q  a# W+ S2 H2 A$ N$ p所得结果：

- i" w( l7 D4 i0 s
dist =
# X! |4 k9 b  v# J

5 l/ [' o; H7 P     0    -2     1     3    -1     2     5     8
5 F5 H8 n9 c2 g/ h: G
8 l, M0 |- ?' |" i, x, M7 S

2 k/ H6 Y  B2 c/ V; O. g
pre =
( q* g1 r* u1 P4 R' _$ M

- [. i4 J$ S! P- T+ i$ U   NaN     1     1     6     2     5     4     5

( T% Q, b1 A8 n
( f' t9 l4 ^3 [2 J% k" m
5 e- [$ h; l# k9 m3 R4 I/ b8 b; n$ O
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
  u$ m: l. P1 @- S/ D3 [, y$ G" J代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！