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为源点标号
for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
( Q: T, H! L3 H. R+ X, d, O    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
% N) e+ y& i- h* L8 s! qfor k=1:n-1
( U9 p' E1 H# k    for i=1:n %松弛操作
5 d( a' o0 O+ }        for j=1:n
1 M6 U+ g9 l4 I: c2 h3 c% ]            if d(i,j)~=inf
0 g  N$ J8 ?4 S! h1 h* z                if dist(j)>dist(i)+d(i,j)
7 d$ i; M  q, _  u                    dist(j)=dist(i)+d(i,j);
8 c% h4 g6 c/ X9 ^" y& V) [                    pre(j)=i;
' w; T0 ]- ]% E' N  I                end
+ d' r; W6 ?6 ~, j; i% V/ ]1 y            end
: Q. I- B& b* a        end
5 v/ `9 y+ l" R) j0 L    end
end
( \; K8 b2 e1 ]! ]1 ?- U# Yfor i=1:n
    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
( ]! |% Z# ]* B, q8 x                error('Negetive WeightCircut');
9 r# \& L& `; g            end
# t2 v9 e2 o( Q        end
    end
end
$ Q6 R1 ~/ u  O! w" N6 W9 Q+ Zdist
( N! O  X, i; w1 X( [( Dpre
: Y$ q" w' x! N% d6 w' Gend
1 D: Y8 V4 y' B- I+ 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;...
# c, o" A0 z: w' o( f. Q9 ]0 e      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
& `0 J+ R' d$ M3 v. c- `% b      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
* @: j& R2 f5 e5 m* J' I3 fi=1;m=8;

2 F& d8 ^% T) mBellman_Ford(w,m,i)
' n( G7 H6 B5 f%%%%%%%
# p& I& t; c5 l  p. \+ u; `所得结果：


0 T# n* b) V! @/ ?dist =

6 h; _. ?) L) F# U' v9 f; y
2 Q2 J3 u/ S& @" [     0    -2     1     3    -1     2     5     8

7 E: A. b3 h. z* _( U0 Z

% u! J$ y* y: o" i- K4 A9 t3 A
pre =
& j  ]/ U+ h6 s

   NaN     1     1     6     2     5     4     5


0 c# Y' g: r$ w
: J" J2 g0 i# Z( }! I
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
# u, D3 ]# E' p: ]* P6 o6 _7 p代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！