Floyd 算法

计算机科学中的Floyd-Warshall算法是一种用于查找带正或负权重边的有向加权网络中最短路径的方法（但没有负循环）。 它有时被称为Floyd算法、Roy-Warshall算法、Roy-Floyd算法或WFI算法。 该算法将在一次运行中发现所有顶点对之间的最短路径的长度（总权重）。 尽管该算法不返回关于路径本身的信息，但仍然可以重建路径。 该方法也可用于确定加权图中所有顶点对之间的最大路径，或（与Schulze投票系统相关）关系的传递闭包 R。

历史和命名

Robert Floyd于1962年首次发布了Floyd-Warshall方法，它是动态规划的典型例子。 它与Kleene的算法（于1956年发布）密切相关，该算法用于将确定性有限自动机转换为正则表达式，但它基本上与Bernard Roy在1959年和Stephen Warshall在1962年先前发布的用于查找图的传递闭包的算法相同。 Peter Ingerman于1962年将该方法的标准版本作为三个分层的for循环引入。

对于解决所有最短路径对问题，请使用Floyd Warshall算法。 找到带边加权的定向图中每对顶点之间的最短距离是该任务的目标。

在加权网络中，这是一种用于确定每对顶点之间最短路径的算法。 该算法使用动态规划方法来确定最短路径。

以下是针对N x N图的C函数。 该函数跟踪矩阵cost [N][N]中每对的最短路径。 提供的图的成本矩阵可在cost Mat [N][N]中访问。

Floyd Warshall算法

• 首先，将解决方案矩阵初始化为与输入图矩阵相同。
• 然后通过将每个顶点视为中间顶点来更新解决方案矩阵。
• 计划是每次选择一个顶点并更新使用所选顶点作为中间顶点的任何最短路径。
• 在选择顶点编号k作为中间顶点时，已经考虑了顶点0、1、2、..、k-1。
• 对于每对源和目标顶点（i，j），分别有两个潜在的结果。
• 从i到j的最短路径不包括k作为中间顶点。 我们保留当前的dist[i][j]值。
• k是从i到j的最短路径中的中间顶点。 如果dist[i][j] > dist[i][k] + dist[k][j]，则我们将dist[i][j]的值更新为dist[i][k] + dist[k][j]。
• 以下图像描述了所有对最短路径问题中上述最优子结构属性。

输出

The following matrix shows the shortest distances between every pair of vertices 
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0
................................................
Process executed in 1.11 seconds
Press any key to continue.

说明

上述程序仅输出最短距离。 通过将先前的数据放入单独的2D矩阵中，我们可以更改方法以同时显示最短路径。

此外，限制中的INT_MAX可以用作INF.h的值，以确保我们处理可行的最大值。 为了防止算术溢出，当我们将INF作为INT_MAX时，我们必须修改上述程序中的if条件。