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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
- s; f4 u; T3 D: s  Rfunction Bellman_Ford(d,n,s)
3 u0 l# b5 s! D' P+ }%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
$ ~: ^9 v0 M' w' B    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
- W$ d6 j) O3 d: D* w& p. Q* i! Jend
0 Q7 b7 a1 l$ r, `, R/ Jdist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
6 T4 F7 D0 S9 r            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
4 B) t* n/ B5 y) [/ n                    pre(j)=i;
' D# [  p9 |  x% C2 R7 g                end
+ R2 n+ K* a8 ], a2 |; \            end
' [, R5 A: N4 f0 g        end
    end
end
+ q/ l3 q1 V9 q& {. B6 `/ mfor i=1:n
    for j=1:n
        if d(i,j)~=inf
" T- X: f% B8 ~+ c            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
; S6 F3 [1 y* x7 H& b                error('Negetive WeightCircut');
5 {2 U1 B& G: N9 E            end
# O" a/ S8 `7 D: v        end
    end
2 R6 r2 ]  J/ D9 d: u$ {; Fend
dist
+ ]8 o5 {9 k" F1 x2 R  Ipre
7 ?, ^5 K, [9 _+ y+ W/ I6 H" [end
2 A0 W0 S7 ?& }" D%%%%%%%
运行如下代码：
clc;clear
) G) c1 h. w# w# m8 @' b+ Hw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
& v& u0 Z/ T: M" g% F; S  q      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;

5 ^. T# Q* w+ {4 @8 g) t6 {Bellman_Ford(w,m,i)
%%%%%%%
所得结果：
4 j2 v/ K; x8 i0 V7 U' a1 u! ]
1 a% n4 B8 L6 A9 `+ V; p
dist =


     0    -2     1     3    -1     2     5     8
: ~% L( B3 ?, I# D


4 y# C' `- }- k) o, z; F9 R3 m% B
, l; t9 E) w2 u$ j& L4 qpre =

; C6 m6 ~8 A7 J
2 _( ?) O9 g" r* J4 }! g4 R- y   NaN     1     1     6     2     5     4     5


, S( f3 m4 Z# b4 ^; g* k  v& R

) P2 K, {* V+ l% @  G2 s结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
2 T9 ^1 [% o2 G5 M* x, u) I代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！