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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
3 _- f: t# K- a& f; sfunction Bellman_Ford(d,n,s)
7 A( J2 f, \) H1 s6 N%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
- f9 M; S9 J' o4 j! R3 E    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
8 _! q# d& i, lend
. h5 j6 D' V! T2 o' udist(s)=0;
, ~& n; y) J2 lfor k=1:n-1
    for i=1:n %松弛操作
: }3 n8 y, A# [8 s5 l* \: A: }        for j=1:n
5 S& f7 D7 L! C; m! A, a            if d(i,j)~=inf
, y- V# R" {- [) l                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
+ i  m& R% N! a7 [- h! _                    pre(j)=i;
                end
% i( Y5 L4 B* a, |4 Y5 @            end
        end
    end
* S& ]7 ~3 z, ?: v9 {$ yend
. \" T& @# P* Z# I& ^1 tfor i=1:n
    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
. m4 s5 f# S: C0 ?) P        end
    end
) B4 v6 X: S* I, \end
dist
pre
end
%%%%%%%
4 L7 o+ p) H6 W8 C- Z! O* N运行如下代码：
, O* h# {5 }4 z6 n( |1 }0 ?clc;clear
' [* k+ n) b: d- _: P1 N, g/ J: gw=[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 g% P9 G, f+ U" S+ w6 A- F      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
9 V% d, H$ Q! N' ]) S& t5 m      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;
0 o2 v- D: E/ G8 F- p
% C3 v6 T$ J. r! e1 t0 tBellman_Ford(w,m,i)
%%%%%%%
9 j* G/ i; M$ e9 E: h所得结果：

5 g6 O/ Y3 w# q( G0 Q
, M& a1 J& G2 @+ B6 w: u& N3 w. o1 ydist =
& g$ X2 p7 ]1 T
: E/ V1 N- c* E! F
     0    -2     1     3    -1     2     5     8

* R3 S' _2 z* G

* ^0 H: u0 o+ r' C% \1 T
pre =


1 L/ X+ i2 y$ O) D   NaN     1     1     6     2     5     4     5

  p7 R  ~" W4 I8 C  Y
5 n9 s" U& h! `# D% m' p! C

结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
- x& P1 q! K5 }9 x% C7 R' S4 S" B代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！