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)
" ~+ u" u* m, h& d( s9 |%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
5 R( j& Z8 r2 O- e( o" e    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
# M6 O5 A; M! A, g2 cend
dist(s)=0;
+ ?, G9 d0 T$ s: J* ?+ _9 Q) Ufor k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
, I9 D, l* Z* w" j! Z& u* m2 U                if dist(j)>dist(i)+d(i,j)
( V) I2 V2 C' N0 a# \                    dist(j)=dist(i)+d(i,j);
+ Z1 u; ~% h9 ?" r" }8 Y                    pre(j)=i;
                end
            end
8 W6 m/ u* J9 _7 H        end
    end
end
for i=1:n
3 Q7 ?. R; @4 `6 }$ ^+ m' R/ x/ ?5 C    for j=1:n
+ x) E5 u! [8 x# g. i. l9 i        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
) H3 w% h+ S- Y) c2 J$ A: O            end
        end
    end
# Z; e1 q% w  X7 w2 u* y) h# Send
dist
3 ]7 y' l( P; Y9 I. @  B8 spre
) G2 q) @$ t; Y. P9 |& Yend
%%%%%%%
运行如下代码：
5 P- D% }9 S( |) j6 Yclc;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;...
      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
- q6 R) |0 G1 v! O; U0 vi=1;m=8;

Bellman_Ford(w,m,i)
) X( W2 ]! f3 q+ p4 z' g* R$ ~%%%%%%%
5 |2 U0 s1 k6 |+ X所得结果：
1 ^; Z2 J- y+ c0 M  |( L$ B5 H
2 y: r- o, p+ ]4 K
% C; o8 t1 k; A" F+ `: @: `8 |8 w' |& Kdist =


     0    -2     1     3    -1     2     5     8

# B' y5 k6 H) ^2 x: G3 a# H
5 c$ P* m3 l( S0 n

1 Q, @4 k4 S: c- O+ P$ j6 ]pre =
& P4 i6 c$ o  [
! a& p& m) R( T* w5 [9 R: {" L
; n4 [. A9 u/ A3 {   NaN     1     1     6     2     5     4     5
  E  e2 O- S/ ^( J. l7 Z# z
$ j* p. s" P& Q) [( u


结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
, r4 s2 T: T' P: Y9 T2 e' `: X代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！