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为源点标号
2 p1 Q) E! k$ d! Kfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
! J/ U2 D& M5 s: i6 o4 N( Q$ mdist(s)=0;
for k=1:n-1
) m$ Y# F* d7 H    for i=1:n %松弛操作
# I4 T- z$ d3 w, y6 ^; J        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
            end
        end
    end
end
6 ~& C0 U5 ?2 j9 |0 Tfor i=1:n
2 l( \- d! G+ C. Q" L1 ]    for j=1:n
* b1 e, p4 L: H0 a        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
* B3 R# p7 K1 u        end
. d* Q2 e, U' g    end
end
dist
pre
. q4 b# Z- B0 Z" Wend
; y' k0 }+ M% o+ k%%%%%%%
  Q: ~- Z, x/ |; p+ Q% `+ S运行如下代码：
clc;clear
5 B" @* e) U+ q0 x- c; A- 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;...
      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0]
2 c8 }, Z- y+ s- wi=1;m=8;

( e: |. J0 O5 n4 uBellman_Ford(w,m,i)
; ~; Q/ \* e; q9 o% _; A' O) I%%%%%%%
- p$ Q, h4 n7 p* H9 j7 J4 Q所得结果：
, \/ @( h4 _/ A' Z. w+ j/ v

, r% Q5 Y, i& M/ [: Edist =
( R9 \; o  {+ b+ I
2 I! Z6 x9 u" K$ T' N
2 @! H  f% A- a2 @     0    -2     1     3    -1     2     5     8




pre =


   NaN     1     1     6     2     5     4     5
* H) |( ^4 S9 n/ j0 I1 h1 [/ K4 B5 w
; V. I" q+ K1 n8 q* Z$ {2 \3 t
8 X. {% x. ]; U

# J6 X( X; i' _$ d1 \/ e" O# R结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
, W" A+ t5 }, k3 v代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！