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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
function Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
/ ~. [7 C' q$ f" @  Nfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
: O% S0 i- Y3 u    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
: P( k: z: [2 I1 r% Tend
dist(s)=0;
' l: |$ K/ _- D7 X" Y6 E6 efor k=1:n-1
* s% @% x/ T0 R) d* h* D    for i=1:n %松弛操作
. V1 ~; j+ K6 G4 }7 `1 f( Q9 r        for j=1:n
( S2 o0 J4 A$ u& u2 Z* J4 D9 d& t6 |            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
& R4 a# ~; n  c8 D$ |% B- k! L                    pre(j)=i;
) o6 S3 d) _  q; G                end
5 x/ L3 t4 k7 P7 T/ Z: b+ i# v            end
- R; O9 G% l: `7 G: c" R; V        end
! ^: ?0 X; i" }! o1 O    end
end
for i=1:n
    for j=1:n
0 \7 e: `) N$ l# d0 \- G% z% U        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
6 I# g$ I/ b0 R- x: g$ Z* v                error('Negetive WeightCircut');
            end
9 t* J: ~5 D: t8 h; ^        end
3 ^! f' a1 r2 t, B8 \% c. X    end
+ |/ a0 O$ h6 \end
dist
pre
, {. \  t, M( Y3 p: i/ Nend
. T. ]( r8 D" u3 W4 H) K8 J9 }. l%%%%%%%
运行如下代码：
clc;clear
+ w+ a- f9 o7 I  d$ Cw=[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;...
2 ]; u1 T3 D, r' j+ Y7 G      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;
* P/ ~: s8 ^; o
+ [; ^0 |6 C9 i6 f9 [% o: hBellman_Ford(w,m,i)
4 f) q5 S+ {# V. L: `% M  _: G1 k%%%%%%%
所得结果：
( |/ z8 J$ z; x6 y5 [% S
$ v: `) Y$ e; i! x: m' n3 ~
dist =

# n1 h5 H" {6 Z' F5 y7 }1 v$ i) d
5 G/ o" O8 i6 h- z8 @3 U: v+ L     0    -2     1     3    -1     2     5     8

( P& {6 O( v5 I# ]% d* ?
  M; s% M! H  S6 J9 T$ g+ J$ h8 }

/ C  s+ z- ^$ Q; {% m# zpre =
5 J9 t! k! U9 Q! S% s% a9 N$ K
9 Y# _; S! ]- g# \( g
   NaN     1     1     6     2     5     4     5
5 p: \7 s" X' f6 a% q$ e6 _



结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010