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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
! O( e+ l4 x( p5 a7 H1 ufunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
& J& ]) u5 ~9 i" H( C+ \for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
3 A9 N' r- t! L9 N+ vend
dist(s)=0;
for k=1:n-1
" }% }. ~+ h( C0 n6 W' E: Z( @    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
1 U% L* I' g6 i$ @6 e; q                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
- a3 L* A9 E, T8 J( W" [            end
        end
    end
! Q7 Y  C( F! _) R# nend
& W: _3 a8 @& c# Efor i=1:n
5 B& L9 S! ]: M# O! p1 K    for j=1:n
        if d(i,j)~=inf
! M: U7 R' V1 q# S, h9 ^            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
7 L+ ^1 {; |' i7 {9 Q9 w        end
2 Z0 f4 u: S  j) F$ m0 u7 _; u    end
: f7 _7 r# Y% U% eend
- I1 t; h7 X6 u" H- }8 vdist
pre
end
%%%%%%%
运行如下代码：
clc;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;...
) t3 P3 I1 Y) {' m1 o" w      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;

Bellman_Ford(w,m,i)
%%%%%%%
所得结果：


dist =
' c. X/ P8 v* I0 I/ w" ]
  Q9 N! f! N- C4 {) Y& B. }0 y0 R
     0    -2     1     3    -1     2     5     8



7 `3 y! T' t2 U( _: \
pre =
  u( k. x" N; d  }9 `5 J) ~

& B, s4 v! `% c) ~! u% U  g   NaN     1     1     6     2     5     4     5
- |& @+ Z7 i. j5 X


" Z( O: t" M- _" v! ]: s3 X
, d& |1 i4 G' o8 B& |结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
' B6 c, o- D, ?# G# w! b6 \代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010