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)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
+ P1 R/ O% A, |4 Jfor i=1:n %初始化dist，pre
* Q2 j# y% v( q  W5 U    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
, K% g% g- c' d7 Bdist(s)=0;
for k=1:n-1
, t. M" Q$ t' }# T8 z" V+ q    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
/ n9 A4 q& \9 C( K  D$ Y                if dist(j)>dist(i)+d(i,j)
4 F4 T9 G& C5 T, `) B                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
/ a$ z8 R5 F, ^9 S' X0 j* ^2 P                end
+ l' g, e; K0 L" x8 d! G3 \, }            end
- u  d  I, _5 }* i        end
: `$ f+ m& z& L: t4 H- Z5 q+ O    end
end
for i=1:n
    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
        end
& k4 T# k2 Q, w" J  e# q3 t! w8 I; ^    end
- {- s9 s7 n* X0 Aend
dist
pre
+ `) f9 J& q) X/ v, X# lend
%%%%%%%
运行如下代码：
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;...
) j9 Z& l9 m) f: ^+ z      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
4 ~+ A$ v' P4 A5 ~* [i=1;m=8;

Bellman_Ford(w,m,i)
# Y& Q$ W9 P+ C" m/ x/ J%%%%%%%
所得结果：
" ]0 F! w/ ^6 c0 ^, a2 y

, x4 F$ U2 U" C* J0 Kdist =

8 p3 `# G  N2 S5 p2 J' e7 K- r
     0    -2     1     3    -1     2     5     8

9 j6 c) R" m1 ?3 C% V1 z( q6 b, r
2 M- J1 _' L7 X+ `! R/ P
6 J- a, V4 @4 |4 j$ Y, D
pre =
5 H# ?5 a: S' n% E" j6 [) h

* R! M( W9 \" Z8 {) P* t2 E# X   NaN     1     1     6     2     5     4     5

( Z1 {9 K" V, r8 r0 T; q' |$ @

# e+ h' \4 ?( n7 b0 f2 ^. d
结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
- \. [' M  L4 ~  L代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！