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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
3 I! j/ j1 h3 Y' H1 D9 {, tfunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
- [' r. V1 k, w* Y    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
/ m! {" f) h9 ]end
8 \) [8 e, @1 [5 }1 n% Idist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
0 P2 ]) ?* r) }        for j=1:n
$ @2 F* `9 K' H! D( }            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
$ I' S8 q/ H+ t" ]4 r& f                    dist(j)=dist(i)+d(i,j);
' Z# N4 D; B4 I/ }- D& c) a% Q                    pre(j)=i;
' k0 v8 @6 f1 N/ O. U6 B                end
: Z4 ^2 V: O5 M5 b( H4 o9 f9 `            end
& Y1 E, o% i+ ^, ]  a        end
2 B; V4 K$ g* n: x- `    end
end
for i=1:n
    for j=1:n
0 Z, H7 i/ Q0 e8 W5 I( u" n* s' K( a        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
. C: x, v+ Q0 z            end
        end
    end
: g+ U( N' K8 j1 c6 L8 T6 nend
9 S7 y' G, p3 n9 V& tdist
pre
: z7 t; F3 ~) L; c! mend
9 u) H. b) P# g+ R! @! n) q%%%%%%%
运行如下代码：
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;...
) d& t" K4 o% j; o      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
4 F( b$ i: K' i      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
  B0 q' _- \. q$ M6 Ji=1;m=8;
* g: |9 @6 G2 P0 `- J; K
+ b6 H! L' t* M( e9 r& Y% n: X, \Bellman_Ford(w,m,i)
%%%%%%%
$ C; \$ [. k' m. c$ B所得结果：


* I& ~9 e8 N# O* @. p! V. K4 tdist =


3 N/ a. x* `, k     0    -2     1     3    -1     2     5     8
) R# D4 v9 f- i, v# H  r1 A



pre =

8 O# s/ R, {6 a/ m, C
6 U2 F: ~* {, X6 f; @$ M   NaN     1     1     6     2     5     4     5

9 F2 ~1 s( M: S) q$ a

3 `4 r- h- F3 d7 z# ]" b1 C5 `
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！