Floyd-Warshall 算法

Floyd-Warshall 算法是一种动态规划算法，用于发现加权图中的最短路径，包括负权重循环。该算法通过计算图中每对顶点之间的最短路径，并使用中间顶点矩阵来跟踪迄今为止已知的最佳路径。

但在我们开始之前，让我们简要了解一下什么是动态规划。

理解动态规划

动态规划是一种在计算机科学和数学中使用的技术，通过将复杂问题分解为较小的子问题并尽可能简单地解决每个子问题来解决复杂问题。它是一种优化技术，可以通过利用子问题的解决方案来找到解决问题的最佳方法。

动态规划背后的关键思想是将子问题的解决方案存储在内存中，以便在解决更大的问题时可以重复使用它们。这降低了规则集的时间和空间复杂性，并允许它解决比暴力方法大得多和更复杂的问题。

动态规划有两种重要类型

1. 记忆化
2. 制表

记忆化涉及将每个子问题的结果存储在缓存中，以便以后可以重复使用。表格化涉及以自下而上的方式构建子问题解决方案表，从最小的子问题开始，然后逐步扩展到更大的子问题。动态规划广泛应用于优化问题、计算几何、设备学习和自然语言处理等领域。

动态规划可以解决的一些著名问题包括斐波那契数列、背包问题和最短路径问题。

Floyd-Warshall 算法的历史

Floyd-Warshall 规则集由 Robert Floyd 和 Stephen Warshall 于 1962 年独立开发。Robert Floyd 是 IBM Thomas J. Watson 研究中心的数学家和计算机科学家，而 Stephen Warshall 是加利福尼亚大学伯克利分校的计算机科学家。该算法最初是用于运筹学领域，用于解决具有正或负边权重的有向图中的所有对最短路径问题。该问题在运筹学中引起了极大的兴趣，因为它在交通、通信和物流方面有许多应用。

Floyd 于 1962 年在一份题为“算法 97：最短路径”的技术报告中首次介绍了该规则集。Warshall 很快独立发现了该规则集，并在他自己的技术报告“布尔矩阵定理”中发表了它。此后，该算法已成为计算机科学的基石，并广泛应用于研究和行业的许多领域。它能够有效地找到图中所有顶点对之间的最短路径，包括具有负边权重的路径，这使其成为解决各种优化问题的宝贵工具。

Floyd-Warshall 算法的工作原理

规则集的工作原理如下

1. 初始化距离矩阵 D，其中 D[i][j] 表示顶点 i 和顶点 j 之间的最短距离。
2. 将矩阵的对角线条目设置为 0，所有其他条目设置为无穷大。
3. 对于图中的每个区域 (u,v)，更新距离矩阵以反映边缘的权重：D[u][v] = weight(u,v)。
4. 对于图中的每个顶点 k，考虑所有顶点对 (i,j) 并检查通过 k 从 i 到 j 的路径是否比当前最佳路径短。如果是，则更新距离矩阵：D[i][j] = min(D[i][j], D[i][k] + D[k][j])。
5. 在所有迭代之后，矩阵 D 将包含所有顶点对之间的最短路径距离。

示例

Floyd-Warshall 是一种用于查找加权图中所有顶点对之间最短路径的算法。它通过维护一个包含每对顶点之间距离的矩阵，并迭代更新此矩阵直到找到最短路径。

让我们看一个例子来解释 Floyd-Warshall 算法的工作原理

考虑以下加权图

图： 加权图

在此图中，顶点由字母（A、B、C、D）表示，边缘上的数字表示这些边缘的权重。

为了将 Floyd-Warshall 算法应用于此图，我们首先初始化每对顶点之间的距离矩阵。如果两个顶点直接通过边连接，则它们的距离是该边的负载。如果顶点之间没有直接边，则它们的距离是无限的。

在规则集的第一遍迭代中，我们考虑使用顶点 1 (A) 作为所有顶点对之间路径中的中间顶点的可能性。如果从顶点 1 到顶点 2 的空间加上从顶点 2 到顶点 3 的空间小于从顶点 1 到顶点 3 的当前距离，那么我们用这个新距离更新矩阵。我们对每对可能的顶点都这样做。

在第二遍迭代中，我们再次考虑使用顶点 2 (B) 作为所有顶点对之间路径中的中间顶点的可能性。我们像以前一样更新矩阵。

在第三遍迭代中，我们考虑使用顶点 3 (C) 作为所有顶点对之间路径中的中间顶点的可能性。

最后，在第四次也是最后一次迭代中，我们考虑使用顶点 4 (D) 作为所有顶点对之间路径中的中间顶点的可能性。

第四次迭代后，我们得到了图中每对顶点之间的最短路径。例如，从顶点 A 到顶点 D 的最短路径是 4，这是矩阵中 A 行 D 列的值。

Floyd-Warshall 算法在不同编程语言中的实现

我们现在将看到 Floyd-Warshall 算法在 C、C++、Java 和 Python 等不同编程语言中的实现。

C 语言实现代码

以下是 C 语言编写的 Floyd-Warshall 算法实现程序代码。

程序代码

输出

Shortest distances between all pairs of vertices:
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

C++ 中的代码实现

以下是 C++ 编写的 Floyd-Warshall 算法实现程序代码。

程序代码

输出

Shortest distances between all pairs of vertices:
    0    5    8    9
  INF    0    3    4
  INF  INF    0    1
  INF  INF  INF    0

Java 代码实现

以下是 Java 编写的 Floyd-Warshall 算法实现程序代码。

程序代码

输出

0 3 3 5
2 0 2 4
3 1 0 5
5 3 2 0

Python中的代码实现

以下是 Python 编写的 Floyd-Warshall 算法实现程序代码。

程序代码

输出

[0, 3, 7, 5]
[2, 0, 6, 4]
[3, 1, 0, 5]
[5, 3, 2, 0]

理解 Floyd-Warshall 算法的时间和空间复杂度

时间复杂度 - 该算法的总体时间复杂度为 O(N^3)，其中 N 是图中顶点的数量。它适用于具有糟糕权重循环的密集图，因为它可以处理它们而不会陷入无限循环。但是，对于稀疏图，Dijkstra 算法或 Bellman-Ford 算法可能更有效。

当我们谈论时间复杂度时，让我们完成关于为什么 Bellman-Ford 或 Dijkstra 最短路径算法不适合解决包括所有节点对的最短路径问题的未完成讨论。

Bellman-Ford 和 Dijkstra 最短路径算法只计算从一个节点到所有其他节点的最短路径，它们的上限，其中 n 和 m 分别是节点和边的数量，分别为 O(nm) 和 O(n+mlogn)。

此外，Dijkstra 最短路径算法对于负加权边无效。

如果将 Bellman-Ford 算法扩展到包含所有节点，则时间复杂度变为 n*O(nm) = O(n^2*m)。

Floyd Warshall 算法只考虑节点数量，因此有向网络的最大边数可以高达 n*(n-1)，这意味着总复杂度可以高达 O(n^4)。

因此，Floyd-Warshall 算法是更好的选择！

空间复杂度 - 该算法需要一个二维数组，通常称为“距离矩阵”，用于存储图中每对顶点之间的最短路径距离。空间矩阵的大小由图中顶点的数量决定，其空间复杂度为 O(V^2)，其中 V 是图中顶点的范围。

除了空间矩阵，该算法还需要一个二维数组来跟踪任意两个顶点之间最短路径上的中间顶点。这个数组通常被称为“路径矩阵”；它的空间复杂度也是 O(V^2)。

因此，Floyd-Warshall 规则集的总体空间复杂度为 O(V^2)，这意味着算法所需的内存量随图中顶点的数量呈二次增长。对于具有许多顶点的大型图来说，这可能是一个问题，因为该算法可以快速变得内存密集，并且可能无法在内存有限的机器上运行。

Floyd-Warshall 算法的一些优点和缺点

现在让我们讨论一下使用 Floyd-Warshall 算法的一些优点和缺点

Floyd-Warshall 算法的优点包括

1. 它可以发现加权图中所有顶点对之间的最短路径，包括具有负边权重的图。
2. 它是一个简单易于实现的算法，使所有技能水平的开发人员都可以使用它。
3. 它适用于密集图和稀疏图。
4. 它的时间复杂度为 O(N^3)，对于大多数实际应用程序来说相对高效。
5. 它可用于在图中发现负权重循环。

Floyd-Warshall 规则集的缺点包括

1. 它需要一个大小为 N^2 的矩阵来存储中间结果，对于极大的图来说可能过大。
2. 它不是解决某些类型图（包括稀疏图或具有非负边权重的图）中所有对最短路径问题的最有效规则集。
3. 它可能不适用于实时应用程序或具有严格内存限制的应用程序，因为它可能需要很长时间才能计算出非常大的图中的最短路径。
4. 它可能不如其他算法（例如 Dijkstra 算法或 Bellman-Ford 规则集）直观，这使得一些开发人员更难理解。

Floyd Warshall 算法的应用

Floyd-Warshall 算法是一种动态规划算法，用于查找加权图中所有顶点对之间的最短路径。以下是 Floyd-Warshall 算法的一些程序

1. 路由算法： Floyd-Warshall 算法广泛应用于路由算法中，例如互联网路由中使用的 OSPF（开放最短路径优先）协议。它可以帮助确定网络中两个节点之间的最短路径，并有助于找到最不拥堵的路径。
2. 航空公司网络： Floyd-Warshall 规则集还可以用于航空公司网络中，以最低成本找到两个城市之间的最短路径。它可以帮助航空公司规划航线并最大限度地降低燃油费用。
3. 交通网络： 该算法用于在交通网络中查找点之间的最短路径。它可以帮助减少拥堵并改善城市地区的交通流量。
4. 计算机网络： Floyd-Warshall 算法也用于计算机网络中，以确定网络中主机之间的最短路径。它可以帮助最小化社区延迟并改善社区整体性能。
5. 游戏开发： 规则集可用于游戏开发中，以在游戏世界中查找两个对象之间的最短路径。它在玩家需要在复杂环境中导航的游戏中很有用，例如迷宫或城市。

这些只是 Floyd-Warshall 算法的众多应用中的一小部分。它是一种功能强大的算法，可以在广泛的领域中应用于解决大量问题。