python 中的 Warshall 算法与 Floyd 算法有何不同？

Question

我的学校作业是使用邻接矩阵完成这两个任务，但几乎每个 google 搜索都只将 floyd-warshall 显示为一种算法。我已经有了只有弗洛伊德的代码。有人知道 Warshall 算法吗？这两者有什么区别？

Answer 1

欢迎来到 Whosebug。我想您的大部分 Google 研究结果都产生了 Floyd-Warshall 算法。我希望以下内容能够回答您的问题并澄清任何疑问。

首先，Floyd-Warshall 算法解决了所有对最短路径 (APSP) 问题，其目标是找到图中所有节点对之间的最短路径（在您的例子中，表示为邻接矩阵）。该算法之所以有这个名字，是因为研究人员 Stephen Warshall 和 Robert Floyd 独立提出了一个非常相似的策略来解决 APSP 问题。

实际上，原始的 Warshall 算法更简单，因为它只找到图的传递闭包，并且不使用任何关于边权重的信息。 Floyd 的算法基本上是这个算法加上对这些权重的额外考虑。

给定一个 n x n 表示有向图的邻接矩阵 G，其传递闭包是一个布尔值 n x n 矩阵，其中 (i, j) 处的条目等于 true 当且仅当存在从顶点 [=12= 的有向路径时] 到顶点 j。 Warshall 的算法通过重复计算邻接矩阵（每个顶点一个）来找到此传递闭包。让我们调用 W^k 这样的矩阵，其中 0 <= k <= n。 W^0 表示没有任何中间顶点的路径，W^n 的条目设置为 true 当顶点之间存在一条路径时，该路径具有来自图的任何顶点的中间顶点。算法如下：

def warshall(G):
  '''The graph G may be represented by means of a numpy matrix'''

  W = G  # this would be W^0
  n = len(G)
  for k in range(n):
    for i in range(n):
      for j in range(n):
        # (*)
        G[i, j] = G[i, j] or (G[i, k] and G[k, j])

  return W  # this would be W^n

对于 Floyd 算法，输入图应表示为加权邻接矩阵，它与 Warshall 的算法完全相同，但 (*) 行更改为 G[i, j] = min(G[i, j], G[i, k] + G[k, j])。使用最小值是因为目标是最小化整体重量。

python 中的 Warshall 算法与 Floyd 算法有何不同？

How is the Warshall algorithm different from Floyd algorithm in python?

python

adjacency-matrix

floyd-warshall