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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
. p" }# t7 V5 k3 }( t7 H5 Lfunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
, f: `$ f) P( h9 Lfor i=1:n %初始化dist，pre
: {7 }  w9 A% v3 [/ }    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
$ U5 p4 x) b% `0 P3 K) |% ?6 m    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
' n' t8 p/ Z4 Y* s2 Pend
8 T) P, l" t7 a0 N* J: W. k  o7 m" qdist(s)=0;
$ Q. t: D/ P. Q( R" f. Pfor k=1:n-1
    for i=1:n %松弛操作
+ }$ b1 m; a# a$ j% Q" A0 \        for j=1:n
            if d(i,j)~=inf
% p+ K" X$ d/ t+ L2 x' p8 @5 q                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
' U1 z: o2 J. N                    pre(j)=i;
                end
            end
- x- @- C1 @/ W        end
! L; E5 [. n2 U4 A" n9 W/ N    end
, r8 |" S" N; N: `# bend
for i=1:n
    for j=1:n
        if d(i,j)~=inf
' d8 a# ?! R& Y  ^5 b            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
& y* \' J2 [6 p; g                error('Negetive WeightCircut');
( }  |1 f2 x7 A0 W7 \2 {+ |            end
        end
    end
. f$ h, V2 v/ s* H" Bend
- o$ O  Z) s, `. y) z) Qdist
pre
; V+ r7 v' n* `4 E! t% [1 Lend
%%%%%%%
- {: U' ~5 [& L0 c6 U8 z& v" F运行如下代码：
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;...
4 {8 `. m' L, \      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;

4 x1 m) w# @' }Bellman_Ford(w,m,i)
%%%%%%%
所得结果：
9 Y2 n+ y# l" M+ @- _6 O( e

dist =


     0    -2     1     3    -1     2     5     8
* t" A7 s  V/ F* D& y# W/ A

6 b" @! m; t. i! e6 T* M) J

5 E. H' h9 g+ a  N& c8 P# E( dpre =

6 r& o" c6 x. Z- [; t" h
   NaN     1     1     6     2     5     4     5

3 n; U5 k; y9 v6 M* j" @- e
: A2 w- U4 p- A! [* d

+ Z% h3 Q/ x0 K" ^0 I: ~结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
; X( g, F% c3 |6 c1 O代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！