BFM 维基百科翻译

Bellman–Ford算法

维基百科，自由的百科全书跳转到导航跳转到搜索

Bellman–Ford算法

类

单源最短路径问题（针对加权有向图）

数据结构

图形

最坏情况下的表现

{\ displaystyle \ Theta（| V || E |）}

最佳情况下的表现

{\ displaystyle \ Theta（| E |）}

最坏情况下的空间复杂度

{\ displaystyle \ Theta（| V |）}

图和树 搜索算法

清单

相关话题

的Bellman-Ford算法是一种算法，其计算的最短路径从单一来源顶点到所有其他顶点的加权有向图。[1]对于相同的问题， 它比Dijkstra的算法慢，但用途更多，因为它能够处理某些边权重为负数的图形。该算法最初由Alfonso Shimbel（1955）提出，但取而代之的是分别由Richard Bellman和Lester Ford Jr.分别在1958年和1956年发布的。[2] 爱德华·F·摩尔（Edward F. Moore）也在1957年发布了相同的算法，因此有时也称为Bellman-Ford-Moore算法。[1]

在图形的各种应用中发现了负边缘权重，因此该算法很有用。[3] 如果图形包含从源头可以到达的“负循环”（即边的总和为负值的循环），则没有最便宜的路径：在负循环上有点的任何路径都可以绕负周期再走一圈，使价格更便宜。在这种情况下，Bellman-Ford算法可以检测并报告负循环。[1] [4]

内容

算法[ 编辑]

在此示例图中，假设A是源，并且以从右到左的最差顺序处理边缘，则需要使用| V | -1或4次迭代，以使距离估计收敛。相反，如果按从左到右的最佳顺序处理边缘，则算法将在一次迭代中收敛。

像Dijkstra的算法一样，Bellman-Ford通过松弛进行，其中将正确距离的近似值替换为更好的近似值，直到最终找到解。在这两种算法中，到每个顶点的近似距离始终是真实距离的高估，并被其旧值的最小值和新找到的路径的长度所替代。但是，Dijkstra的算法使用优先级队列来贪婪地选择尚未处理的最接近的顶点，并在其所有出站边缘执行此松弛过程。相比之下，Bellman-Ford算法只是放松所有边缘，然后执行此操作{\ displaystyle | V | -1} 时间，在哪里 {\ displaystyle | V |}是图中的顶点数。在每个重复中，具有正确计算出的距离的顶点数量会增加，由此得出的结论是所有顶点最终都将具有正确的距离。与Dijkstra相比，此方法允许将Bellman-Ford算法应用于更广泛的输入类别。

贝尔曼-福特参加 {\ displaystyle O（| V | \ cdot | E |）} 时间，地点{\ displaystyle | V |} 和 {\ displaystyle | E |} 分别是顶点和边的数量。

function BellmanFord(list vertices, list edges, vertex source) is
    ::distance[], predecessor[]

    // This implementation takes in a graph, represented as
    // lists of vertices and edges, and fills two arrays
    // (distance and predecessor) about the shortest path
    // from the source to each vertex

    // Step 1: initialize graph
    for each vertex v in vertices do
        distance[v] := inf             // Initialize the distance to all vertices to infinity
        predecessor[v] := null         // And having a null predecessor
    
    distance[source] := 0              // The distance from the source to itself is, of course, zero

    // Step 2: relax edges repeatedly
    for i from 1 to size(vertices)−1 do //just |V|−1 repetitions; i is never referenced
        for each edge (u, v) with weight w in edges do
            if distance[u] + w < distance[v] then
                distance[v] := distance[u] + w
                predecessor[v] := u

    // Step 3: check for negative-weight cycles
    for each edge (u, v) with weight w in edges do
        if distance[u] + w < distance[v] then
            error "Graph contains a negative-weight cycle"

    return distance[], predecessor[]

简而言之，该算法将到源的距离初始化为0，将所有其他节点的距离初始化为无穷大。然后，对于所有边缘，如果可以通过抓住边缘来缩短到目的地的距离，则该距离将更新为新的较低值。在每次迭代中我其边缘扫描时，算法找到至多长度的所有最短路径我边缘（和可能的一些路径长于我边缘）。由于没有循环的可能的最长路径是{\ displaystyle | V | -1} 边缘，必须扫描边缘 {\ displaystyle | V | -1}时间以确保找到所有节点的最短路径。对所有边缘进行最终扫描，如果更新了任何距离，则为长度路径{\ displaystyle | V |} 已发现只有在图形中至少存在一个负循环时才会出现边沿。

正确性证明[ 编辑]

本节未引用任何资料。请通过在可靠来源中添加引文来帮助改进本节。未采购的材料可能受到挑战并被清除。查找来源：“贝尔曼福特算法” – 新闻· 报纸· 书籍· 学者· JSTOR （2019年3月）（了解如何以及何时删除此模板消息）

该算法的正确性可以通过归纳证明：

引理。在我重复for循环之后，

  • 如果Distance（u）不是无穷大，则它等于从s到u的某些路径的长度；和

  • 如果存在从s到u的路径（最多i个边缘），那么Distance（u）最多是从s到u的最多i个边缘的最短路径的长度。

证明。对于异步的基本情况，考虑i=0和之前的那一刻为首次执行循环。然后，对于源顶点source.distance = 0，这是正确的。对于其他顶点u，这也是正确的，因为从源到u的路径都不存在0条边。 u.distance =`` infinity

对于归纳案例，我们首先证明第一部分。考虑一下顶点距离更新为的时刻 v.distance := u.distance + uv.weight。通过归纳假设，u.distance是从源到u的某些路径的长度。然后u.distance + uv.weight是从源到v的路径的长度，该路径的长度沿着从源到u的路径 ，然后到v。

对于第二部分，请考虑从源到v的最短路径P（可能有不止一条），最多具有i个边缘。令u为该路径上v之前的最后一个顶点。然后，从路径的一部分来源，以ü是从最短路径源到ü至多I-1的边缘，因为如果它不是，那么就必须有一些严格的短路径源到ü最多与I- 1条边，然后我们可以将边uv附加到此路径，以获得一条最多具有i的边界严格小于P－矛盾。通过归纳假设，u.distance在i -1迭代之后，最多是该路径从源到u的长度。因此，uv.weight + u.distance最大为P的长度。在第i 次迭代中，v.distance与进行比较uv.weight + u.distance，如果uv.weight + u.distance较小，则设置为等于。因此，在i次迭代之后，v.distance最多为P的长度，即，从源到v的最短路径的长度最多为i个边缘。

如果没有负权重循环，则每个最短路径最多会访问每个顶点一次，因此在步骤3中无法进行进一步的改进。相反，假设无法进行任何改进。然后对于顶点v [0]，...，v [ k -1]的任何循环，

v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight

围绕循环进行总结，v [ i ] .distance和v [ i -1（mod k）]。distance项抵消，从而使

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

即，每个周期的权重均为非负数。

寻找负周期[ 编辑]

当使用该算法查找最短路径时，存在负循环是一个问题，从而阻止了该算法找到正确的答案。但是，由于它会在找到负循环时终止，因此Bellman-Ford算法可用于寻求该目标的应用程序，例如在网络流量分析中的循环取消技术中。[1]

路由中的应用[ 编辑]

Bellman-Ford算法的分布式变体用于距离矢量路由协议，例如路由信息协议（RIP）。该算法是分布式的，因为它涉及自治系统中的多个节点（路由器），自治系统是ISP通常拥有的IP网络的集合。它包括以下步骤：

  1. 每个节点计算自身与AS中所有其他节点之间的距离，并将此信息存储为表格。

  2. 每个节点将其表发送到所有相邻节点。

  3. 当节点从其邻居接收到距离表时，它会计算到所有其他节点的最短路径，并更新其自己的表以反映所有更改。

在这种情况下，Bellman-Ford算法的主要缺点如下：

  • 它的伸缩性不好。

  • 由于更新是逐节点传播的，因此无法快速反映网络拓扑的变化。

  • 如果链路或节点故障使某个节点无法从其他一组节点到达某个节点，则计数到无穷大，这些节点可能会永远花时间逐渐增加其对与节点的距离的估计，并且与此同时可能存在路由环路。

改进[ 编辑]

通过观察以下事实，可以在实践中（尽管不是在最坏的情况下）改进Bellman-Ford算法：如果算法主循环的迭代在不进行任何更改的情况下终止，则可以立即终止该算法，因为随后的迭代将不再进行任何更改。在这种提前终止条件下，在某些情况下，主循环使用的数量可能少于| |。V | − 1次迭代，即使算法的最坏情况保持不变。

Yen（1970）对没有负权重循环的图描述了Bellman-Ford算法的另外两个改进。再次，虽然在实践中使算法更快，但他们并没有改变其算法。{\ displaystyle O（| V | \ cdot | E |）}最坏的情况是时间限制。他的第一项改进减少了算法每次迭代中需要执行的松弛步骤的数量。如果顶点v的距离值自上次松弛v以来没有变化，则无需再次使v之外的边缘松弛。这样，随着具有正确距离值的顶点数量的增加，在每次迭代中需要放松的输出边缘的数量会减少，从而为密集图节省了时间常数。

颜的第二个改进是首先在所有顶点上分配一些任意的线性顺序，然后将所有边的集合划分为两个子集。所述第一子集，ê ˚F，包含所有边缘（v 我，v Ĵ），使得我 < Ĵ ; 第二个E b包含边（v i，v j），使得i > j。每个顶点按v 1，v 2，...，v |的顺序访问。V |，从E f的那个顶点放宽每个输出边缘。然后按v | |的顺序访问每个顶点。V | ，v | V | −1，...，v 1，从E b中的那个顶点放宽每个输出边缘。在第一个迭代之后，算法主循环的每次迭代都会在其松弛距离与正确的最短路径距离匹配的一组边缘中至少添加两个边缘：一个来自E f，一个来自E b。此修改从|减少了算法主循环的最坏情况迭代次数。V| − 1至{\ displaystyle | V | / 2}。[5] [6]

Bannister＆Eppstein（2012）的另一项改进是用随机置换代替了日元第二次改进中所用顶点的任意线性顺序。这种变化使Yen的改进变得最糟（最短路径的边缘在两个子集E f和E b之间严格交替）极不可能发生。使用随机排列的顶点顺序，主循环中所需的预期迭代次数最多为{\ displaystyle | V | / 3}。[6]

琐事[ 编辑]

在中国，还增加了一个先入先出队列的Bellman-Ford算法，被称为算法SPFA，由爱德华·摩尔在1959年，1994年出版，重新发现了Fanding段，深受谁参加学生国家省 [ zh ] 省信息奥林匹克竞赛和国际大学编程竞赛。[7]

笔记[ 编辑]

  1. ^ 跳至：a b c d Bang-Jensen＆Gutin（2000）

  2. ^ 作者（2005）

  3. ^ Sedgewick（2002）。

  4. ^ Kleinberg＆Tardos（2006）。

  5. ^ Cormen等人，第二版，问题24-1，第614-615页。

  6. ^ 跳转到：一个 b 见塞奇威克的幅练习为算法。，第4版，演习5和12（检索二○一三年一月三十○日）。

  7. ^ Duan, Fanding (1994), "关于最短路径的SPFA快速算法", Journal of Southwest Jiaotong University, 29 (2): 207–212

参考[ 编辑]

原始资料[ 编辑]

  • Shimbel，A.（1955年）。通信网络中的结构。信息网络研讨会论文集。纽约，纽约：布鲁克林理工学院的理工出版社。第199–203页。

  • 理查德·贝尔曼（1958）。“关于路由问题”。应用数学季刊。16：87-90。MR 0102435。

  • 福特，小莱斯特·R。（1956年8月14日）。网络流理论。论文P-923。加利福尼亚州圣莫尼卡：兰德公司。

  • 摩尔，爱德华·F（1959）。穿过迷宫的最短路径。程序 国际交流。座谈会。转换理论，1957年，第二部分。马萨诸塞州剑桥市：哈佛大学。按。第285–292页。MR 0114710。

  • 颜金Y（1970）。“在通用网络中找到从所有源节点到给定目的地的最短路径的算法”。应用数学季刊。27：526–530。MR 0253822。

  • 密西根州班尼斯特；Eppstein，D.（2012年）。Bellman-Ford算法 （PDF）的随机加速。分析算法和组合学（ANALCO12），日本京都。第41–47页。arXiv：1111.5414。Bibcode：2011arXiv1111.5414B。

次要来源[ 编辑]

分类：

Previous【研究】参考文献Next陵墓

Last updated