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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
, W" W9 U) N( N9 Yfunction Bellman_Ford(d,n,s)
# v$ s# ?, P; g/ [' Y6 o! V+ g%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
; ~/ Y" @# P5 [* yfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
4 l3 A$ F/ v8 D/ j$ s1 ~- eend
dist(s)=0;
for k=1:n-1
1 S5 @4 _+ {% o0 _    for i=1:n %松弛操作
2 f' J6 D& ^2 X& y& |        for j=1:n
7 ]  j- E0 i. \' }. H            if d(i,j)~=inf
  }2 f6 C% c6 n/ N. v2 B7 w                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
. U; H1 c6 I# p; Q6 L; A                end
) N: l. w6 M/ R            end
        end
9 F+ j8 x6 A$ U* [, m/ p$ w    end
$ o* G. V# U0 o- z8 r; @% {6 B7 hend
for i=1:n
9 T, E; _7 i2 u* [3 V5 r7 G& G) J' v( j    for j=1:n
& I0 t# i; g( X        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
& w- K# |. a" j# ^3 V3 w+ ^        end
& [% \* S" S' A& j9 Z$ N4 P8 s    end
. o# I5 j6 l. V- y* f5 ^) oend
: |. w0 f8 m; a# Vdist
* N# {: R, W, A# d+ zpre
4 h( H' G4 C9 a% send
: K4 ?' y" h  g( D) o$ _* ^- J%%%%%%%
运行如下代码：
/ |$ q9 W4 B! I' c5 C, Uclc;clear
, Y9 R0 S" q4 J, xw=[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;...
      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
" s( j6 @0 a/ R5 o) Ji=1;m=8;
& F& K, @  N( T5 e
Bellman_Ford(w,m,i)
%%%%%%%
所得结果：
3 \: Z* ^$ F( V% r1 u/ ?/ ]; F/ t

dist =

  G2 C- @6 r: ~; c1 T  O
     0    -2     1     3    -1     2     5     8
1 t5 s/ q% h6 v5 _

7 m4 k3 }; n. j5 C

$ i9 w0 |: D) u: `8 v& d* dpre =
' L* Q* K- U. }( ~- {  F4 |
$ Q% l% z" `2 Q+ c% J$ o
   NaN     1     1     6     2     5     4     5

' x9 W$ G% |& s1 B! z! Z) H, u


结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
& v& J* l3 F* d6 P  o) ~3 w. _) o代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！