The Wayback Machine - https://web.archive.org/web/20221028221218/https://baike.sogou.com/kexue/d10089.htm

WarShall算法

编辑

在计算机科学中，弗洛伊德-沃肖尔算法是一种在一个有正或负边缘权重(但没有负循环)的加权图中寻找最短路径的算法。[1][2] 单次执行算法将找到所有顶点对之间最短路径的长度(加权总和)。虽然它不返回路径本身的细节，但是可以通过对算法的简单修改来重建路径。该算法的各种版本也可用于寻找关系R的传递闭包，或(结合舒尔茨投票系统)加权图中所有顶点对之间的最宽路径。 该算法的版本也可用于查找关系的传递闭包    ，或(与 舒尔茨投票系统相关) 加权图中所有顶点对之间的最宽路径。

1 历史和命名编辑

弗洛伊德-沃肖尔算法是动态规划的一个例子，1962年由罗伯特·弗洛伊德以目前公认的形式出版。[3] 然而，它本质上与伯纳德·罗伊在1959年[4] 和史蒂芬·沃舍尔在1962年[5] 为寻找图的传递闭包而发表的算法相同，[6] 并且与克莱尼的算法(1956年发表)密切相关，该算法用于将确定性有限自动机转换成正则表达式。[7] 同样在1962年，彼得·英格曼首次描述了算法的现代表述，即三个嵌套的for-loops。[8]

该算法也被称为弗洛伊德算法、罗伊-沃肖尔算法、罗伊-弗洛伊德算法或WFI算法。

2 算法编辑

弗洛伊德-沃霍尔算法比较每对顶点之间通过图的所有可能路径。它可以通过图形中的   次比较来实现这一点。考虑到图中可能有多达   条边，并且每条边的组合都经过测试，这一点非常显著。它是通过逐步改进两个顶点之间最短路径的估计，直到该估计是最优的这一流程来实现的。

考虑顶点V编号为1至N的图G。进一步考虑一个函数   仅使用集合   中的顶点作为中间点返回从i}到j可能的最短路径。现在，给定此函数，我们的目标是仅使用   中的顶点找到从每个i到每个j的最短路径。

对于每对顶点，shortestPath(i,j,k)可以是

(1)不经过顶点k(仅使用集合{1,2,…,k-1}中的顶点)的路径。

或者

(2)经过顶点k (从i到k，然后又从k到j，两条路径都仅使用{1,2,…,k-1}中的中间顶点)

我们知道从i到j仅使用顶点1到k-1的最佳路径由shortestPath(i,j,k-1)表示，并且明显地，如果从i到k再到j存在更好的路径，则该路径的长度将是从i到k的最短路径的串联(仅使用{1,2,…,k-1}中的中间顶点)

如果w(i,j)是顶点i和j之间的边的权重，我们可以按照以下递归公式定义:边界情况是shortestPath(i,j,0)=w(i,j)

递推公式为：

shortestPath(i,j,k)=min⁡(shortestPath(i,j,k-1),shortestPath(i,k,k-1)+shortestPath(k,j,k-1)

这个公式是弗洛伊德-沃霍尔算法的核心。该算法首先对所有(i,j)对计算当k = 1时的shortestPath(i,j,k)，然后计算k=2等情况。这个过程一直持续到k =N，并且我们已经使用任何中间顶点找到了所有(i,j)对的最短路径。这个基本版本的伪代码如下:

弗洛伊德-沃霍尔算法比较每对顶点之间通过图的所有可能路径。它可以这样做    图表中的比较。考虑到可能有高达    图中的边，并且测试边的每一个组合。 它是通过逐步改进两个顶点之间最短路径的估计来实现的，直到该估计是最优的。

考虑一个图表    顶点    编号1到    。进一步考虑一个函数    从返回最短可能路径    到    仅使用集合中的顶点    作为中间点 一路上。 现在，给定这个函数，我们的目标是从每个函数中找到最短的路径    给每个人    仅使用中的顶点   。

对于每一对顶点    可能是

(1)一条路径 没有 通过    (仅使用集合中的顶点   。)

或者

(2)一条路径 做 通过    (从    到    然后从    到   ，两者都只使用 中间的 顶点在    )

我们知道    到    只使用顶点的    穿过    由定义   很明显，如果有更好的方法    到    到   ，那么该路径的长度将是从    到    (仅使用 中间的 顶点在   )以及从    到    (仅使用 中间的 顶点在    )。

如果    顶点之间的边的重量    和   ，我们可以定义    在以下方面 递归的 公式:基本情况是

  

递归的例子是

  

  

  。

这个公式是弗洛伊德-沃霍尔算法的核心。该算法通过首先计算来工作    尽管    成对的   那么   等等。 这个过程一直持续到   ，我们找到了所有人的最短路径    使用任何中间顶点的对。这个基本版本的伪代码如下:

1 让 dist是一个|V| × |V|最小距离数组，初始化为∨(无穷大)
2 每个人 边缘(u,v)
3    [区u][v] ← w(u,v)  //边缘的重量(u,v)4 每个人 顶点 v5    [区v][v] ← 0
6 为 k 从 1 到 |V
7    为 i 从 1 到 |V
8       为 j 从 1 到 |V
9          如果 [区i][j]>[区i][k]+[区k][j]
10             [区i][j] ← [区i][k]+[区k][j]
11         结束if

3 例子编辑

上面的算法在下面左边的图表上执行:

在外部循环的第一次递归之前，即上面标记为k = 0，唯一已知的路径对应于图中的每一条边。在k = 1时，找到了穿过顶点1的路径:特别是，找到了路径[2，1，3]，取代了边较少但更长的路径[2，3]。在k = 2时，会找到穿过顶点{1，2}的路径。红色和蓝色方框显示了路径[4，2，1，3]是如何从先前迭代中遇到的两条已知路径[4，2]和[2，1，3]组合而成的，其中顶点2是这两条路径的交点。不考虑路径[4，2，3]，因为[2，1，3]是迄今为止从2到3遇到的最短路径。在k = 3时，会找到穿过顶点{1，2，3}的路径。最后，在k = 4时，找到所有最短路径。

每次k迭代的距离矩阵，更新后的距离用粗体表示，将为

k = 0 j
1 2 3 4
i 1 0 ∞ −2 ∞
2 4 0 3 ∞
3 ∞ ∞ 0 2
4 ∞ −1 ∞ 0

k = 1 j
1 2 3 4
i 1 0 ∞ −2 ∞
2 4 0 2 ∞
3 ∞ ∞ 0 2
4 ∞ −1 ∞ 0

k = 2 j
1 2 3 4
i 1 0 ∞ −2 ∞
2 4 0 2 ∞
3 ∞ ∞ 0 2
4 3 −1 1 0

k = 3 j
1 2 3 4
i 1 0 ∞ −2 0
2 4 0 2 4
3 ∞ ∞ 0 2
4 3 −1 1 0

k = 4 j
1 2 3 4
i 1 0 −1 −2 0
2 4 0 2 4
3 5 1 0 2
4 3 −1 1 0

4 在有负循环情况下的表现编辑

负循环是边的总和为负值的循环。在构成负周期一部分的任意一对顶点i、j之间没有最短路径，因为从i到j的路径长度可以任意小(负数)。为了有数值意义输出，弗洛伊德-沃霍尔算法假设没有负循环。然而，如果有负循环，弗洛伊德-瓦尔应算法可以用来检测它们。方法如下:

弗洛伊德-沃霍尔算法迭代修正所有顶点对之间的路径长度（i,j），包括其中i = j；

最初，路径(i,j)的长度为零；

只有当路径长度小于零，即表示负周期时，{\displaystyle [i，k，\ldots，i]}才能对此进行改进；

因此，在算法之后，如果存在从i回到i中存在的负长度路径， (i,j)将为负。

任何一对顶点之间都没有最短的路径   ,    其形成负循环的一部分， 因为从    到    可以任意小(负)。 对于数值上有意义的输出，弗洛伊德-沃霍尔算法假设没有负循环。 然而，如果有负周期，弗洛伊德-瓦尔应算法可以用来检测它们。 直觉如下:

  • 弗洛伊德-沃霍尔算法迭代修正所有顶点对之间的路径长度    ，包括在哪里    ；
  • 最初，路径的长度     为零；
  • 一条路     只有当长度小于0，即表示负周期时，才能对此进行改进；
  • 因此，在算法之后，     如果存在从     回到    。

因此，要使用弗洛伊德-沃肖尔算法检测负循环，可以检查路径矩阵的主对角线，存在负数表示该图至少包含一个负循环。[9] 为了避免数值问题，应该检查算法内部for循环中路径矩阵对角线上的负数。[10] 显然，在无向图中，一条负边会产生一个包含顶点的负循环(即闭通路)。将上述示例图的所有边视为无向的，例如顶点序列4–2–4是权重总和为2的循环。

5 路径重建编辑

弗洛伊德-沃霍尔算法通常只提供所有顶点对之间的路径长度。通过简单的修改，可以创建一种方法来重建任意两个端点顶点之间的实际路径。虽然人们可能倾向于存储从每个顶点到另一个顶点的实际路径，但这不是必需的，事实上这是极其占用储存空间的。相反， 最短路径树可以通过一种时间复杂度为   空间复杂度为   方法计算出来，这一方法使得我们高效地从任意两个连通的顶点间重建最短路径。

取而代之的是 最短路径树 可以为中的每个节点计算    时间使用    存储每棵树的内存，它允许我们从任意两个相连的顶点高效地重建路径。

let dist be a  array of minimum distances initialized to  (infinity)let next be a  array of vertex indices initialized to nullprocedure FloydWarshallWithPathReconstruction ()   for each edge (u,v)
      dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
      next[u][v] ← v   for k from 1 to |V| // standard Floyd-Warshall implementation
      for i from 1 to |V|         for j from 1 to |V|            if dist[i][j] > dist[i][k] + dist[k][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]
               next[i][j] ← next[i][k]procedure Path(u, v)   if next[u][v] = null then
       return []
   path = [u]   while u ≠ v
       u ← next[u][v]
       path.append(u)   return path

让 dist be a 
  
  
   
    
     
      
     
     
      
     
     
      
     
     
      
     
     
      
     
     
      
     
     
      
     
    
     初始化为的最小距离数组 
  
  
   
    
     
      
     
    
     (无穷大)让 下一个是a 
  
  
   
    
     
      
     
     
      
     
     
      
     
     
      
     
     
      
     
     
      
     
     
      
     
    
     顶点索引数组初始化为 空程序 带路径重建的floydwarshall ()   每个人 边缘(u，v)
      [区u][五世] ← w(u，v)  //边缘的重量(u，v)
      下一个[u][v] ← v   为 k 从 1 到 |V //标准弗洛伊德-沃肖尔实现
      为 i 从 1 到 |V         为 j 从 1 到 |V            如果 [一区][j]>[一区][k]+[k][j] 然后
               [区i][j] ← [一区][k]+[k][j]
               下一个[i][j] ← 下一个[i][k]程序 路径(u，v)   如果 下一个[u][v] =空 然后
       返回 []
   路径= [u]   而u ≠ v
       u ← 下一个[u][v]
       path.append(u)   返回 小路

6 分析编辑

让   表示   ，即顶点的数量。要从   中得到所有   个   (针对所有i和j)需要进行   次计算。由于我们从   开始计算   矩阵序列   ，   ，…shortestPath   ，因此使用的操作总数为   因此，算法的复杂性是   .

7 应用和推广编辑

弗洛伊德-沃肖尔算法可用于解决以下问题:

  • 有向图中的最短路径(弗洛伊德算法)
  • 有向图的传递闭包(瓦尔沙尔算法)。在瓦尔沙尔最初的算法公式中，图是未加权的并且是用布尔邻接矩阵表示。然后加法运算被逻辑与(AND)取代替，最小运算被逻辑或(OR)代替
  • 找到一个正则表达式来表示一个有限自动机所接受的正则语言(克莱尼算法，一种与弗洛伊德-沃肖尔算法密切相关的推广)[11]
  • 实矩阵反演(高斯-乔丹算法) [12]
  • 最优路由。在这个应用中，人们感兴趣的是找到两个顶点之间具有最大流量的路径。这意味着，不是像上面的伪代码那样取最小值，而是取最大值。边权重表示流量的固定约束。路径权重代表瓶颈；所以上面的加法运算被最小运算所代替
  • 探路者网络的快速计算
  • 最宽路径/最大带宽路径
  • 计算差界矩阵(DBMs)的标准型
  • 计算图之间的相似度

8 实现编辑

实现可用于许多编程语言。

C++，boost::graph库中

C#，QuickGraph中

C#，QuickGraphPCL中(QuickGraph的一个分支，通过使用Portable Class Libraries（PLCs）使其具有更好的项目兼容性)。

Java，Apache Commons Graph中

JavaScript， Cytoscape库中

MATLAB，Matlab_bgl包中

Perl，Graph模块中

Python，SciPy库(模块scipy.sparse.csgraph)或NetworkX库中

，e1071和Rfast包中

9 与其他最短路径算法的比较编辑

弗洛伊德-沃肖尔算法是计算稠密图中所有顶点对之间路径的好选择，在稠密图中，大多数或所有顶点对通过边连接。对于具有非负边的稀疏图来说，更好的选择是从每个可能的起始顶点使用Dijkstra算法，因为当明显小于时，重复Dijkstra算法的运行时间(    使用 斐波那契堆s)比    弗洛伊德-沃霍尔算法的运行时间    明显小于   。(使用斐波那契堆的情况下)的运行时间优于Floyd–war shall算法的运行时间对于具有负边但没有负循环的稀疏图而言，可以使用约翰逊算法，其渐近运行时间与重复的Dijkstra算法相同。

也有已知的算法使用快速矩阵乘法来加速密集图中所有对的最短路径计算，但是这些算法通常对边缘权重做出额外的假设(例如要求它们是小整数)。此外，由于运行时间中的常数因子很高，只有对于非常大的图时，他们才能提供比弗洛伊德-沃霍尔算法更快的速度。

参考文献

  • [1]

    ^Cormen, Thomas H. （英语：Thomas H. Cormen）; Leiserson, Charles E. ; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.CS1 maint: Multiple names: authors list (link) See in particular Section 26.2, "The Floyd–Warshall algorithm", pp. 558–565 and Section 26.4, "A general framework for solving path problems in directed graphs", pp. 570–576..

  • [2]

    ^Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5th Edition. Addison Wesley. ISBN 0-07-119881-4..

  • [3]

    ^Floyd, Robert W. (June 1962). "Algorithm 97: Shortest Path". Communications of the ACM. 5 (6): 345. doi:10.1145/367766.368168..

  • [4]

    ^Roy, Bernard (1959). "Transitivité et connexité". C. R. Acad. Sci. Paris. 249: 216–218..

  • [5]

    ^Warshall, Stephen (January 1962). "A theorem on Boolean matrices". Journal of the ACM. 9 (1): 11–12. doi:10.1145/321105.321107..

  • [6]

    ^埃里克·韦斯坦因. "Floyd-Warshall Algorithm". MathWorld..

  • [7]

    ^Kleene, S. C. (1956). "Representation of events in nerve nets and finite automata". In C. E. Shannon and J. McCarthy. Automata Studies. Princeton University Press. pp. 3–42..

  • [8]

    ^Ingerman, Peter Z. (November 1962). "Algorithm 141: Path Matrix". Communications of the ACM. 5 (11): 556. doi:10.1145/368996.369016..

  • [9]

    ^Hochbaum, Dorit (2014). "Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths" (PDF). Lecture Notes for IEOR 266: Graph Algorithms and Network Flows. Department of Industrial Engineering and Operations Research, University of California, Berkeley..

  • [10]

    ^Stefan Hougardy (April 2010). "The Floyd–Warshall algorithm on graphs with negative cycles". Information Processing Letters. 110 (8–9): 279–281. doi:10.1016/j.ipl.2010.02.001..

  • [11]

    ^Gross, Jonathan L.; Yellen, Jay (2003), Handbook of Graph Theory, Discrete Mathematics and Its Applications, CRC Press, p. 65, ISBN 9780203490204..

  • [12]

    ^Penaloza, Rafael. "Algebraic Structures for Transitive Closure"..

阅读 980
版本记录

  • 暂无