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为源点标号
7 a, d9 s  l, ~7 V3 h% E' Cfor i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
* S1 J/ c5 v: I3 H    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
7 _; w  i6 u' R% S3 _for k=1:n-1
    for i=1:n %松弛操作
        for j=1:n
3 R0 F" s% I) Y5 E& f3 Z8 |            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
: Q0 ]* P- _2 D# b  T% l7 Y                    pre(j)=i;
                end
+ f5 R' V7 z9 J: B( ]4 j2 ?            end
. G7 o- P! M8 ]- E        end
& _* ~' U8 N! ?6 i/ P    end
end
for i=1:n
    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
1 q- ?+ ?; K; p" C" ^& ?                error('Negetive WeightCircut');
1 G5 P* H0 c9 e0 `- \& t            end
        end
    end
end
dist
* V1 |  l! {4 cpre
end
%%%%%%%
6 O* L, l. k! |$ j' S) g运行如下代码：
clc;clear
, Y9 P; J1 L% O6 R$ a' _3 Jw=[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]
* L- A. O. P7 i( j) K1 \i=1;m=8;
; {7 Q1 s) ?' a5 E# }
Bellman_Ford(w,m,i)
& L* D) }& n& u%%%%%%%
8 O% D! i9 u* Q3 y) U所得结果：

* d6 b( |* U5 Q2 s; Y, o1 K
dist =

$ e1 M  F) F- }! L" ^
     0    -2     1     3    -1     2     5     8




1 M* f! i8 j, q9 Jpre =
8 A. j1 p+ k) x2 h" q) C2 a0 w9 }
3 ^3 ]' Z0 s; H
   NaN     1     1     6     2     5     4     5


& O' B. |- ^: s9 J" @

结果有负数，不知是不是最优结果。求大神帮忙！！！谢谢大神！
; ~, r* }: S1 D# w2 ?6 H代码copy自百度百科。

jt202010

maruibing

路过……

782915935

，额

782915935

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

cmd2.com电影

我也来了，哈,看一看

hdzhangliang

你这权值就有负的啊！