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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
! T+ f; O7 K, w8 ?1 Ofunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
. u" j# a8 E: \- {! b; ~- ~1 i    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
' \% x' d! t' r1 F            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
8 e; c5 }( k% H! i3 p                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
0 S* n: x0 D0 v$ B" l: ~: e                end
            end
        end
    end
' o3 q& g% T: o& Uend
for i=1:n
- E! @8 x$ l2 t+ @8 [, p    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
6 G  q" K/ ?% h" ~" w% d                error('Negetive WeightCircut');
& \6 D* v6 O/ K( E7 Z: l            end
        end
    end
end
dist
pre
+ h& k4 |5 t; \: Y; Hend
%%%%%%%
运行如下代码：
clc;clear
" b, C* ]$ A5 Ww=[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;...
9 `+ I3 N$ d( G      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
i=1;m=8;
& E4 l- m' u$ V* |; e" {
( ]( I7 E; H+ k8 dBellman_Ford(w,m,i)
%%%%%%%
所得结果：


+ R: q- R2 R/ {( mdist =


     0    -2     1     3    -1     2     5     8


% i- J5 b0 O. p2 O7 F" D9 T$ \! ^( L

pre =

; e+ U1 I8 G; ?
   NaN     1     1     6     2     5     4     5
& U1 i2 ~( l: e6 Q" f/ ^



$ X; r% g1 }. ]& C结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
5 d2 K& R  `' p" u代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！