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为源点标号
; Z$ k+ E* U+ a. ofor i=1:n %初始化dist，pre
. F+ @: G. ~$ t0 }# j8 e    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
( `- h( O$ d7 g) ~6 r! r; x6 _6 _end
dist(s)=0;
- @4 ^+ |  L8 c2 Z+ h: S; C3 lfor k=1:n-1
1 u5 D# X# p3 w! K2 D1 h  j8 o7 T# b    for i=1:n %松弛操作
0 C, ?' q) o* n5 u) ^, E9 W  w        for j=1:n
- z8 M" ~% f2 K            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
) P7 R! g6 {: K) ]; f            end
* C4 N+ v6 r) S        end
    end
end
2 W+ u# E  A9 Y% Y+ v; B' Bfor i=1:n
- d4 C2 @  k6 K5 m3 k% ]    for j=1:n
, B4 U: p( l. m9 j        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
9 _' N1 e; H7 F* [0 ^4 `4 n) B                error('Negetive WeightCircut');
9 ]) p2 x$ b( t0 p+ [            end
" m6 R, a7 ~# r, E* e5 U        end
) y5 z* O" C% U0 ^5 D; l* J5 C! m    end
end
dist
pre
6 [1 a0 }# x$ L" A2 n! X6 Kend
7 N8 ]0 R% i( c/ i% ?2 ~) }%%%%%%%
) Z( M! e+ \/ d$ Z0 [1 ~& W: Q运行如下代码：
. f9 U; S8 P; R/ j! v0 r, x; D4 E4 Y) \8 ~clc;clear
! a& U' H4 L5 Lw=[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;...
. E+ z' {" m$ I5 j$ G+ `) E/ r      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
, h: [3 m. t$ A1 T* G& oi=1;m=8;
9 A* R( V" u+ h* [0 b: l- m
Bellman_Ford(w,m,i)
. V+ q# }/ h+ w6 K%%%%%%%
9 G0 {! y. a. l) a1 w  `所得结果：
$ B, h1 ]  z: a+ f- p9 b) ]# Y
2 ?/ j3 q7 h% B+ R! h. Y, `" @) @
dist =
' W. V, x0 ]; K; w  D
5 d6 A6 M7 z: e( M# H" R
& w" T$ J, J% ]' c; p. E     0    -2     1     3    -1     2     5     8
% C) p+ K& U, \& J, N5 G2 c



* J$ `3 k5 X; I! f7 ^pre =
# o3 V) w9 Y/ o6 M5 I8 v0 v

   NaN     1     1     6     2     5     4     5
9 A) b6 [# ]4 p( t% z- d  V
4 q0 t& w2 A5 [  t0 R/ H$ N% y3 Z
9 }$ ]$ ~1 A( p8 c+ o) M$ c' q8 x' Y
, i( Z) Y) J0 ~; [2 f. ~
' m/ |2 }# j' C9 a# }% I结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！