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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
! u. O& W0 k7 qfunction Bellman_Ford(d,n,s)
9 r% ^5 m; ~  D- ]; e! d: K% i%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
* [3 T" Z" z' j# _end
dist(s)=0;
for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
            if d(i,j)~=inf
6 M$ \, ~' h( U5 S5 c: b) V/ d7 {                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
! g$ A5 v/ N0 A1 z# i8 [& Y6 }                    pre(j)=i;
                end
            end
        end
8 D7 s+ f/ N* Z. q7 `+ ]/ j; P: K    end
2 E5 y3 U( L/ aend
for i=1:n
    for j=1:n
( P4 M# o2 Y9 h0 U        if d(i,j)~=inf
0 ^9 \* @8 A" R& e3 Z            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
4 P% Z2 r* }8 m$ K            end
        end
    end
. s. T1 }# H! u% {# C0 Wend
/ _- M9 }8 p+ {; c7 z$ y7 ndist
pre
end
; `; p- z$ {3 w%%%%%%%
( S( ?; ~+ X" v5 {- U! f运行如下代码：
# Z" }6 d5 A$ W+ |0 I* Aclc;clear
; b0 q9 r/ W6 Nw=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
4 \! r6 a  Y: d0 e( a: p      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]
) m/ K( `7 [% gi=1;m=8;

Bellman_Ford(w,m,i)
%%%%%%%
' J9 t5 {0 n7 h9 w  r所得结果：
3 b3 N! H& H2 E$ U
) T0 H' @) d, o0 A% g
6 R, U$ B- H0 i7 o( t( P. wdist =

9 S* d6 K' S4 H+ Y, {9 \
- O7 B) w! E# f3 L4 `' R     0    -2     1     3    -1     2     5     8




pre =
2 F2 C/ ]! e9 d

   NaN     1     1     6     2     5     4     5
7 A/ w) `- B+ X9 l3 `



. S3 N0 K& v, h0 C2 L) G: _) k结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！