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)
/ G' \- F! K) E0 w" r9 j$ G" M%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
) X2 J$ Y+ R$ N2 S8 ffor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
: y% c  W" [) R0 [4 Iend
dist(s)=0;
1 ^7 D/ b  ?8 y# D* u2 b+ @for k=1:n-1
- o8 h( x1 G% v* J; r    for i=1:n %松弛操作
$ z$ c9 F3 H, o- X$ y9 f2 S  B        for j=1:n
  M0 F& {0 I! }% V$ v# E/ m. R            if d(i,j)~=inf
/ ^* S; @: z9 p. P/ I( x                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
/ s, h' g. @- A4 k                end
            end
        end
    end
+ O; n, u3 n# W( B5 A$ W2 Y5 xend
for i=1:n
    for j=1:n
( d, z5 V, B6 X9 @; J0 x- o: v        if d(i,j)~=inf
' [  Q/ v( @4 j2 u+ P( {" P            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
6 W- [- R, j- }# K2 t                error('Negetive WeightCircut');
( b# e- c: C) d1 z2 `            end
        end
    end
% E: ~; b3 m7 d5 D& g; e  K, J9 wend
dist
4 L1 X6 z# v! ?3 z- M3 Ypre
end
& ~# Z  e( E% S6 a% z: v- }' r%%%%%%%
运行如下代码：
! x7 O4 L/ b# }% j( Y- X; |clc;clear
# k0 t2 T" o, Z! I- X: sw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
- w8 K% d/ G" c, ?9 i+ 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;...
5 U" c- K2 {( K. [1 G6 T6 b; ]      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;

" s" P2 w% `# \$ ]+ T* Y( MBellman_Ford(w,m,i)
3 t2 b; A3 @3 O- `" a%%%%%%%
: Q# j; t+ i1 A4 G5 l$ X% E所得结果：

  X) P! ]& s) ^! \5 C
3 q3 J2 w" Z+ pdist =

2 {/ m' u1 I. v/ S
     0    -2     1     3    -1     2     5     8


! w* Z6 M1 v3 d( G4 O6 b

pre =
. B0 V' x- \7 O7 k: g

( z' V5 H7 A4 z7 H   NaN     1     1     6     2     5     4     5
! x& V  {, S( G  A/ b& ~/ l



! N1 m& x/ H8 U$ U2 H  u结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
% C7 H* s& Z* q3 `7 n代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！