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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
( Z% q* a/ B1 B: ofunction Bellman_Ford(d,n,s)
4 c9 n* m# L" _$ V$ z%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
, h/ Z9 S$ g( n% R, J/ I) Jfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
, w) |: f* f( j" e. W    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
4 e! ~: V  C% y$ \5 aend
  V2 z5 X+ U* n, C* o) J% \) ^5 R# jdist(s)=0;
' c3 E8 E$ {' T& ]8 F2 ^( y: K$ u( gfor k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
6 B4 g" A5 A3 z2 I                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
# r/ ?: i& f/ I            end
        end
! Y2 w* p6 \- |1 b* L# @    end
) K, k$ p1 S/ q$ a$ Cend
* h; s9 I* s! ?4 d) q  x$ efor i=1:n
    for j=1:n
. U( M: ^1 w0 Z        if d(i,j)~=inf
  N; j" W* D& Y' W! z. R            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
' b+ e' h8 c4 l) Q                error('Negetive WeightCircut');
            end
3 n& n9 \: D4 n/ e; W0 c2 U        end
    end
& [( Q: |$ I. f! W* w+ D% Q* ?end
dist
& \1 o" d" s. Upre
& ^( p( Y0 S- G4 Q- U2 kend
%%%%%%%
运行如下代码：
clc;clear
/ e& B4 I0 q1 h& z3 jw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
  a: W/ q% `9 s3 N0 X      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
& Q% m  u& M2 B# R) L- Z2 S      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)
" Q0 R" ]( v  @8 D0 j%%%%%%%
所得结果：


+ [! m- h1 `. u$ rdist =

$ k# Z  P9 S+ [# i( o4 ?$ }
# r+ `; u+ u4 P* Z1 m2 t     0    -2     1     3    -1     2     5     8

5 @: m( d; c: f" f; D0 m0 J) G, O# Y
1 Z5 g9 X) M$ a. S/ u+ }% c4 ~
2 j5 `& R2 w4 v) S& r. F
pre =
  [7 N) j' x7 ]6 E
+ ^8 l9 T$ e0 l6 J! O  y
+ p% L2 [* |- J   NaN     1     1     6     2     5     4     5


1 c- u# `) Z7 |2 X
% F& O% q6 @2 |( W, b3 S
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
7 _; w, ]" Y% |5 }  L( g% j+ [代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！