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为源点标号
' f8 j& [: f2 w! }7 J- c- s! r( hfor i=1:n %初始化dist，pre
9 N: U, }. \0 F! j5 J( b( H! y2 G    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
6 y) q' h7 d) e" J8 L    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
/ O/ M( \- y- M8 N9 I8 Jend
dist(s)=0;
& Z) V6 x2 |8 y5 {4 E# Cfor 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);
$ W7 ]3 L+ i% C7 Z( J                    pre(j)=i;
                end
8 K2 G7 i2 a  F; Z" H4 V            end
        end
$ _) o! G2 N  F    end
# [7 G7 V* `. g0 h  N3 Vend
) F1 A# b% n$ K; \% S! b( efor i=1:n
    for j=1:n
        if d(i,j)~=inf
3 T0 p/ b3 K7 k* m! a            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
2 X7 O0 o3 }6 Y# K8 y            end
1 g5 S: s) L/ A" K% D( x5 b) D        end
7 ?; a8 E3 X2 T( w9 V* N    end
; A! l* w8 W: u5 E# Send
dist
  b) O7 Q2 \4 Q$ h/ }/ hpre
4 Y3 e. Q3 |/ ?5 o/ Pend
. F. D* @+ w0 N%%%%%%%
运行如下代码：
0 ?2 R0 i4 a( c) _: W/ l8 l5 F- Zclc;clear
* |( F( l' P# r; e" gw=[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;...
      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
# l4 s" ]" C6 I1 w# G+ Zi=1;m=8;
- V( C8 u$ B. b8 X; M
Bellman_Ford(w,m,i)
7 K2 k6 S. O1 O1 g5 J%%%%%%%
) X) W: E# }4 I' [# C$ p& \8 Z所得结果：
! w, Q3 `1 a4 _* |" P: C

1 h8 ~2 r( F5 y2 z- {) @4 Sdist =

* t; p. Q2 h- c
: H* @2 ~+ z' F8 _1 g. a     0    -2     1     3    -1     2     5     8


! H1 i5 M# h/ `, S; w
; A6 q! `% r% o, l
pre =


   NaN     1     1     6     2     5     4     5

$ S8 }  C0 E# `


# a4 ?' T& l7 q( K5 l0 ~2 ?结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
8 w/ b. K% G# m& _9 A: Q代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！