Bellman-Ford算法,对给定的带权图G=(V,E),其源点为s,加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值,表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路,算法将给出从源点s到图G的任意顶点v的最短路径D[v]。算法代码如下:3 m5 g0 Q& w" ~$ Y+ o" b/ j C: m) o
function Bellman_Ford(d,n,s)# u* }# u& [( \% E, A
%d为已知图的邻接矩阵,n为顶点数(各顶点标号为1,2,...,n),s为源点标号: f6 h2 d9 W6 b) D
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 %松弛操作$ I, x, e- c3 s1 N0 z: S
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)1 Q# ]1 M* n9 ^8 U/ r( D1 T. j+ B
dist(j)=dist(i)+d(i,j);6 w# g+ G" [2 n
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# Rend4 f6 A! m$ L$ x
for i=1:n' K# {& G$ r2 t4 }8 b
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/ t! A( A4 Q B* l2 ^( W! c5 M+ P
end0 w% r7 M+ R# L6 W/ o# ?# X1 @. N; t
end % R* t u9 Y. h; @4 |1 F+ p5 jend( z( ?0 I, y: q5 q- \7 h( u
dist ( V. ^7 ?, w+ v1 R- I+ e, `* kpre) {, e8 \* ?( o- O) {+ J! W, Z9 P
end; i+ C7 k( C- Z% H. z
%%%%%%% ! b: T/ y ~% g( F: P3 j% Z$ a运行如下代码: # H3 v* L; J. y: K( Q6 \0 ?clc;clear( R0 i7 p6 h p" b$ c
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;+ f6 t" |+ Q" M" a7 H
; j' U& r& i7 Z# O; M5 U9 F/ X
Bellman_Ford(w,m,i)) F' M; E5 H0 K* W
%%%%%%% " N: o- f, V" f( |5 p所得结果: 0 D! H' z. H9 L; L* A" X" J7 a, Z- }9 v
4 ?! k$ X5 }) 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 83 p0 g/ ~, N! [% J5 Y' C$ d" ^
?; d. q+ o6 ^1 j; D2 ~$ O' g3 }% R" Z8 N$ i3 H8 v
& K3 |# r9 H6 ^9 b. X % [7 D! z7 O! f; j1 o* H: Y6 ppre = , @. P, U0 K R! @/ q$ N3 P8 I9 d3 G. p) o1 P& m3 _' m
. o" o1 l/ K A' u3 ` NaN 1 1 6 2 5 4 5! E4 f2 u4 q( g
& w) H1 M/ r7 X" P
; d5 c" V6 g5 ?0 I R
; M, C ^4 [& g
2 X) V2 N* Y! N
结果有负数,不知是不是最优结果。求大神帮忙!!!谢谢大神!% }# ^3 \' s$ s1 x' [: a1 S! K
代码copy自百度百科。