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

bb556

Bellman-Ford算法，对给定的带权图G=(V,E)，其源点为s，加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下：
4 B% ?7 s( F2 t# O  _  }  tfunction Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2,...,n），s为源点标号
8 T$ m% |* j* N: a! L% Efor i=1:n %初始化dist，pre
6 x' V8 a& s& B  F% s: ^) Y    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
( E, O' u) Q0 {; Q# R9 r' l% ^    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
% Z7 [8 @) R% ~: b, H$ Oend
dist(s)=0;
( Y9 [, U. J" ?9 l$ c6 F" Mfor k=1:n-1
1 x2 R* b& R0 A* W) ~  i    for i=1:n %松弛操作
  X' S+ a3 h9 q* ?5 B1 J0 d8 {0 |% d        for j=1:n
            if d(i,j)~=inf
2 z2 `" T9 @, e4 N3 Z                if dist(j)>dist(i)+d(i,j)
  N2 b( c* L7 q1 D2 s5 a                    dist(j)=dist(i)+d(i,j);
2 U! w2 F$ s$ r                    pre(j)=i;
                end
0 O" J6 x" n) M  I4 R            end
" N# Z0 |6 B* R9 e7 h1 S. P' o; t        end
% e+ P6 {2 f# a9 Q8 Z    end
end
for i=1:n
8 l5 ^6 i) y' `( w+ O/ X    for j=1:n
5 s, I" V7 u  a' a. ^        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
* B6 Z7 G) t$ u/ x7 x2 \% A; g' i            end
        end
    end
end
; {6 O. a. g) g0 E+ A6 Xdist
pre
end
%%%%%%%
% _; Q9 `  y5 B- ^  |6 G8 t" k  C运行如下代码：
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;...
      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]
( O2 {" p3 X. @* S- s5 ^i=1;m=8;

+ W) W( I0 C, H. L$ u- B# H6 a+ EBellman_Ford(w,m,i)
%%%%%%%
所得结果：
1 \( z; L% e7 ?4 Z3 d

5 ?, }$ a2 O! ~% L. g/ a9 Vdist =

: [; l( C, s0 L5 I2 C6 ^
* Q# `; A, l" C% H# b: H$ h     0    -2     1     3    -1     2     5     8

- d+ _+ z$ T; J) d5 U3 j
" q4 v8 H; o2 q2 B& J

4 F) s% ^+ ^) k* ]& B0 R; M, Zpre =
' Z: `, v; @& U2 d
1 {9 }7 w% g4 H' N9 n
   NaN     1     1     6     2     5     4     5
9 ]& z" m+ G7 i7 x7 j
; \! {1 H0 Y; T' `8 u: w: ~  {) }

% t7 p* N1 M1 y/ e4 l
2 c& |1 P6 L/ }, C4 y2 S结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
- ]" x4 Y. y  q0 \; I) X代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！