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)
% a) r/ k$ |* K' e4 k%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
" j& @  y: b7 S0 `2 n8 v8 `for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
& s8 D. [: O; _" H# g$ @, V; M    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
1 m9 B5 D) N9 H/ |for k=1:n-1
    for i=1:n %松弛操作
9 w6 y4 _' V5 S( @        for j=1:n
            if d(i,j)~=inf
4 q. ~) T5 o3 U5 T: f                if dist(j)>dist(i)+d(i,j)
  n( E5 Q2 ?. x. k+ \                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
2 M5 Z" {7 E  C; B- f+ i8 j* O* X                end
' u4 r/ ^+ f/ d- Q- {            end
8 B- G$ D; q' ~8 D        end
    end
end
$ r# d5 k# I/ `0 C7 h: p( A# mfor i=1:n
    for j=1:n
" k$ ^+ Q" E9 t* _        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
% h& ~  x: S2 h) |        end
    end
( ]" [$ ]7 i1 \5 x8 {" o, @end
2 O/ N* z. G0 g8 hdist
5 c/ G0 `2 J2 vpre
" r6 @: `9 S  m7 @, _end
# a4 [, R! q0 r! n/ A8 Q%%%%%%%
) U6 u$ [1 N( i% z9 {运行如下代码：
clc;clear
  z/ }) x2 \* r6 g) j6 R- Ew=[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]
i=1;m=8;
2 }( ^* z5 D% s0 s, m9 S$ t
Bellman_Ford(w,m,i)
%%%%%%%
所得结果：
, P8 S  x+ C* \0 q( }& d' K

; X" j+ j0 w  ]6 I/ K& c9 Pdist =
/ S& g: _: D7 i3 p4 l1 S$ C
3 C) v$ P2 ?/ B# Z9 k1 _
% {6 \/ N4 S2 m& a     0    -2     1     3    -1     2     5     8
) J' K8 y/ F9 T/ N: @

; b! E2 M4 P5 M) \

5 }6 d0 l2 y( J* W& Z4 p6 ]+ mpre =

6 z& E* k7 Q" W) |7 U) l3 i2 [
   NaN     1     1     6     2     5     4     5


, s! m' [6 r7 q2 `4 Y
) c! x' @* h' A- m+ X0 S2 R1 T; g
5 ^& T* ~) e: M' k结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！