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)
+ o/ C' g& t( ?1 C+ e) Q4 |- O0 b%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
, f. c! @# Y  T, \' @" U    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
$ y% z% U7 `, d7 _end
* T) B" r5 B: W+ R5 w3 H  Q" ~! L' ldist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
' W4 T& s$ p7 C* W            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
/ W: B) q7 r! s. W                    pre(j)=i;
7 w1 |6 U; l4 {                end
( U2 c; V- E3 p! b4 n( S0 _2 P4 l            end
        end
    end
( A, E3 f  W) h. eend
0 y* x( [" p& w" Lfor i=1:n
    for j=1:n
6 o- g6 i% R# X1 n/ f5 X        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
* P) p( v- `7 p: Z! S" p0 q) ~! b        end
+ `( w0 }8 o0 A+ s2 v2 v3 w2 z    end
$ F- |5 y$ r/ }end
5 m" X: h. \1 X: v$ u8 f0 \dist
& q$ Q) h! h6 h* C* gpre
' t9 b. i1 i) v: Z% Q7 p+ rend
%%%%%%%
* K# P3 x# G) _& G运行如下代码：
clc;clear
8 {8 w1 {' {- k% B- aw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
/ f0 M4 A: N, ]& A" J0 B: \; ~      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
  T/ J8 ]8 ]9 |' N- V      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
' X8 Q1 t. N( E8 u7 D' j" o$ ^i=1;m=8;

4 T0 D# ~; b2 \0 OBellman_Ford(w,m,i)
  O# H4 K, W" V. G3 v4 A, H%%%%%%%
* n6 B' C8 j) H9 A$ J$ d) G8 Z所得结果：


* Y9 ~; u2 H- Z7 [- O1 G; A6 Udist =
$ i9 w( w# z' X  g) Y% U
" S% t5 n$ y% f, C+ U1 t
  q4 S" h2 Q% p) X     0    -2     1     3    -1     2     5     8

* r/ a# _7 ^7 m/ `7 l6 h


/ [9 `- Y: k2 t" ^1 k" Q/ ^pre =
: F. ?6 K. n0 \, w$ S: G1 m
  L2 i8 [+ m" U3 ^/ w
- L! c9 U( f: M   NaN     1     1     6     2     5     4     5

/ L  a# Q- x/ A( P0 d- C$ {. l: |* Y
3 m3 D: d* X: n( D% }
, i4 O! X. o* G! f! p) x
: W; j; L' h( |- h5 Y结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！