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)
8 g! b. \& r- G$ Z5 H& v5 |& s%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
& F4 n8 {& W4 q: Xdist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
6 m% a- x+ ~  }$ R1 n        for j=1:n
            if d(i,j)~=inf
, `9 k+ e5 }8 T9 Z                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
) f  z8 Y3 N" s' g  D% G7 f7 {                    pre(j)=i;
7 W+ v7 y! {  q, J  M                end
+ {8 m, T2 p: p/ E- W# @. e4 n/ f            end
& a- u3 }4 r/ |% @: a5 P1 W' e- q        end
    end
end
+ R9 C2 R3 f! b  O; z. M. z3 Hfor i=1:n
; A) V* ?1 @5 d* H' k    for j=1:n
4 z1 Z# q% T! Z6 d        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
        end
    end
' V$ h) q0 K& D0 ]- m2 Y- {end
dist
pre
end
%%%%%%%
/ v3 a. d3 R$ @1 A运行如下代码：
6 U9 M. ~4 z! B/ R* Y. Qclc;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;...
/ o# Q: ]5 A- y0 K$ B$ l      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;
5 ^& p/ c8 ^* T* C# q! J+ ]' \; J
2 o" }* o0 R. B; @0 `8 pBellman_Ford(w,m,i)
%%%%%%%
所得结果：


dist =
& Z4 v& ]( b# z, a9 p

. a& U, F/ P. R7 E     0    -2     1     3    -1     2     5     8

8 E1 w7 t' b8 c+ o7 u


pre =
) R- v' i$ c* d  o; r) f

( I- h# \! S* D6 M   NaN     1     1     6     2     5     4     5

' k( w% t$ x) H6 Y: C: F: w

& |" h9 N8 [3 t& r
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
' `9 O+ f1 }  Y( M' ?代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！