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为源点标号
for i=1:n %初始化dist，pre
$ s) U% S8 C4 r* E5 k    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
; k5 u+ t* Y3 g; C: q' a7 E    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
( g1 W3 x) L& K/ E* N/ k+ m+ s5 ]end
dist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
            end
        end
    end
end
9 Z3 L" a  Y4 Hfor i=1:n
    for j=1:n
. Q- X8 X7 N8 }5 e7 B2 q/ b        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
) _* G5 z; ?5 n* W8 A. K1 {            end
        end
    end
end
% B0 n' K* {% A4 S+ i( Kdist
pre
' x5 N) O$ e: Y# Gend
%%%%%%%
6 A1 a, t3 o+ v: h0 l- }; M运行如下代码：
3 H6 O, D1 |' q; V: x9 U2 lclc;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;...
( v& u& `( G, k1 D# D* R9 _% z      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]
6 W; e* s* f) Y% N/ s5 Oi=1;m=8;

Bellman_Ford(w,m,i)
+ c! f& G0 C# S) k0 l%%%%%%%
+ V1 U! J! s3 s3 i所得结果：
. X% }! a$ s8 D- o% m
! B# \2 I% Q. p/ P) o
6 c3 Q$ t! K- H2 h* z! Q* q' ]dist =
; R5 O- o  ?' X) G* d
3 f* s3 |: e, n  T" k: ^4 D4 A' W
$ S" ~5 x1 ~: [: B0 r: x( r     0    -2     1     3    -1     2     5     8


6 E; D' y- a' w( p

pre =

6 D% y! g2 A; Q# [1 V
. T5 q+ D) x2 N! V1 v$ K( P   NaN     1     1     6     2     5     4     5


0 X( z- [: R9 W

0 p8 w# c" Y9 g结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
5 [7 k5 @% G  H6 Y代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010