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
* }# G* Z2 J5 o2 N    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
' Z" \) S; j: h0 i; M1 ]: h    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
" w" g( O$ u, R$ R4 G' S& Q6 Yend
; @) U: N* Q: d* p, U3 adist(s)=0;
) r' V5 r0 G4 |" z) ?# nfor k=1:n-1
! x5 s" T6 R$ C    for i=1:n %松弛操作
        for j=1:n
" |% y* Z/ S* o# w2 v$ {; ?- X" z* f            if d(i,j)~=inf
- T( F7 r& t" a# R, x6 y                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
5 `1 y* F- \3 U6 q$ t                end
/ I9 w1 {1 x- B) g# i8 N1 u  n            end
" T9 C3 E1 p6 |# R9 `        end
! q% a# D* c7 F1 b6 B( R. w    end
) C/ M* U# i$ O# Rend
for i=1:n
    for j=1:n
( H/ x4 l+ v$ c5 L$ Y1 y& F        if d(i,j)~=inf
( U" |+ V/ i9 J& M2 _! \            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
' G( A1 f( J1 ?$ e                error('Negetive WeightCircut');
6 \  r5 p) h- f4 }( U& ~9 F( V0 H            end
        end
    end
% R* t  u9 Y. h; @4 |1 F+ p5 jend
dist
( V. ^7 ?, w+ v1 R- I+ e, `* kpre
end
%%%%%%%
! b: T/ y  ~% g( F: P3 j% Z$ a运行如下代码：
# H3 v* L; J. y: K( Q6 \0 ?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;...
4 [7 e3 B+ O& Q# c7 N( C      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
! P" y: m& c4 v6 o* W+ Z      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
7 k. E4 {  j, ^7 g. ~1 Y/ c, ii=1;m=8;

Bellman_Ford(w,m,i)
%%%%%%%
" N: o- f, V" f( |5 p所得结果：
0 D! H' z. H9 L; L* A

dist =
5 |0 A: X5 r0 M3 W" u9 S* n0 q
3 X+ `4 |0 E( P8 }- a
4 E: N9 B0 x7 C- @+ t: z; j     0    -2     1     3    -1     2     5     8

  ?; d. q+ o6 ^1 j; D

& K3 |# r9 H6 ^9 b. X
% [7 D! z7 O! f; j1 o* H: Y6 ppre =
, @. P, U0 K  R! @/ q$ N

. o" o1 l/ K  A' u3 `   NaN     1     1     6     2     5     4     5




结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

hdzhangliang

你这权值就有负的啊！

cmd2.com电影

我也来了，哈,看一看

782915935

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

782915935

，额

maruibing

路过……

jt202010