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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
# i4 Y3 o+ \! Tfunction Bellman_Ford(d,n,s)
, K0 @- Q5 ^3 H- C6 @%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
7 y2 T! }  e" I0 |for i=1:n %初始化dist，pre
: c- D  G; X4 T( Z% v* T- L    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
4 u* I+ s8 n: ?+ w8 x    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
+ r' z( X$ N' P5 }9 Q7 f' V" Udist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
" B# ^3 ~: Z# [            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
  E/ e& J3 h; Z6 V) B$ L; c                    pre(j)=i;
/ l/ O$ I8 p: D& |* g. j                end
            end
        end
    end
. V! G0 N5 o; @( X) w- D. pend
, K9 @. i6 [: A0 I, \* ffor i=1:n
0 C4 O6 U' U0 J+ G    for j=1:n
- Z$ p0 M- {' J7 ~: h. d1 m        if d(i,j)~=inf
" `, X. q0 |- U- q! S, e6 ^1 |) H. }            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
* ~' }4 K& {' F            end
        end
; p0 P+ v# x: v    end
7 A0 ~4 O! F: M# k$ `end
dist
pre
end
7 m/ ]: M  i3 I, i%%%%%%%
4 c9 Z# `) d: @4 h; @运行如下代码：
clc;clear
" w6 j8 ]4 M3 x8 Xw=[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;

Bellman_Ford(w,m,i)
$ }) B- w: \( _- A%%%%%%%
所得结果：


, C& J/ D/ k, M, `. }dist =
: h1 z! x6 g: J. a0 e  f' v
7 p9 H  x* C! V" H3 G; r
     0    -2     1     3    -1     2     5     8
6 C. h9 a6 |# Z4 H' b0 b0 M4 h



pre =
% v1 v( n) n$ a

   NaN     1     1     6     2     5     4     5
3 _, D0 Y% _- L  _: o! g2 Y
$ e) g* V. N! t3 f' g& b
9 a" |4 v+ I3 w4 ], R) G

# o4 t: C( g8 ^) I! `7 n结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！