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为源点标号
; E2 x; t3 ]8 g' B+ z# @/ D# hfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
# A3 F8 i2 v$ ~' ^6 Y( L    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
# k3 j9 q7 L4 B/ D/ P& ]; Jfor k=1:n-1
- O7 g+ c. M( I    for i=1:n %松弛操作
        for j=1:n
1 U" ~8 C3 G( S) K. z' S            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
6 n1 s8 z5 h. W6 `4 H" ]9 X& N                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
            end
        end
, g( C0 h  b( q    end
: I$ ^4 o) \1 v2 x# n$ {end
- ~3 k6 b1 o' I& J1 E- qfor i=1:n
    for j=1:n
        if d(i,j)~=inf
/ `2 K( ]! L: a( c            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
0 E; G: f: G+ V# }, o                error('Negetive WeightCircut');
            end
        end
    end
% m  F  x/ r7 s7 {$ k* Dend
' g1 e1 o$ W# J7 jdist
pre
8 S( j0 M) C$ X+ x$ X5 P- rend
%%%%%%%
运行如下代码：
3 f0 K$ T- Q' m& b8 I5 Kclc;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;...
      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
5 V9 l" M+ k  p% M5 z# v& U      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;
* D. W3 d; M2 T$ l9 B' q" l1 e1 M
Bellman_Ford(w,m,i)
%%%%%%%
所得结果：
# z$ Y! w- G. v" z
7 w* Q$ W/ z9 |+ m" C& n
dist =
8 b4 x( `4 e3 {$ n5 w
" C* @5 ~6 e, L( n# g4 _. \
6 L: q* G' [+ V# _! {+ w5 H2 L     0    -2     1     3    -1     2     5     8
% d$ X# b0 k' g. f% N* v# I
' ]) A" U& E3 }9 k6 @; K

- _. `; a" y5 R" W. M2 ]- O
pre =

1 A6 j. F7 ?6 A- L/ T; a; Q
8 s. I. v8 Q/ u3 r& {6 B8 q* Y   NaN     1     1     6     2     5     4     5
. C  T. P7 ~1 K2 i

* d6 [$ @- n; b5 p  E& H

结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
$ |" q# X5 P" I- F. ^4 K  {- l/ M! f代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！