海口市网站建设_网站建设公司_Photoshop_seo优化

弗洛伊德·沃肖算法 Floyd Warshall Algorithm

给定 大小为 的矩阵，其中 表示从节点 到节点的边权重。如果没有直接边， 则设为一个较大的值（例如10⁸）以表示无穷大。对角线元素 为 ，因为节点到自身的距离为零。该图可能包含负边权重，但不包含任何负权重环。dist[][]n x ndist[i][j]ijdist[i][j]dist[i][i]0

你的任务是确定图中所有节点对i 和j之间的最短路径距离。

示例：

输入：dist[][] = [[0， 4， 10⁸， 5， 10⁸]，
[10⁸， 0， 1， 10⁸， 6]，
[2， 10⁸， 0， 3， 10⁸]，
[10⁸， 10⁸， 1， 0， 2]，
[1， 10⁸， 10⁸， 4， 0]]

输出：[[0， 4， 5， 5， 7]，
[3， 0， 1， 4， 6]，
[2， 6， 0， 3， 5]，
[3， 7， 1， 0， 2]，
[1， 5， 5， 4， 0]]
解释：

输出中的每个单元显示了节点到节点的最短距离，该距离是通过考虑所有可能的中间节点，使用Floyd-Warshall算法计算得出的。dist[i][j]ij

试试GfG Practice吧
重定向图标
弗洛伊德·沃沙尔算法：
Floyd–Warshall 算法通过维护一个表示节点间距离的二维数组来工作。最初，该数组仅使用节点之间的直接边填充。然后，算法通过检查中间节点是否有更短路径，逐步更新这些距离。

该算法适用于有向和无向加权图，并且可以处理具有正权和负权边的图。

注意：对于循环为负的图（环中边的和为负）则不适用。

弗洛伊德·沃肖尔算法的理念：
假设我们有一个图的 dist[][]，顶 点从 0 到 V-1 有 V 个。现在我们需要评估一个距离[][]，其中dist[i][j]代表顶点i到j的最短路径。

假设顶点 i 到 j 之间有中间节点。Floyd Warshall 算法背后的理念是将从 0 到 V-1 的每个顶点 k 逐一视为中间节点。当我们考虑顶点k时，必定已经考虑过0到k-1的顶点。因此，我们使用前顶点构建的最短路径，以构建包含顶点k的较短路径。

下图展示了上述弗洛伊德·沃沙尔算法中最优子结构性质：

为什么弗洛伊德·沃肖尔作品（正确性证明）？
该算法依赖于最优子结构原理，即：

如果从 i 到 j 的最短路径经过某个顶点 k，那么从 i 到 k 和从 k 到 j 的路径也必须是最短路径。
迭代方法确保在考虑顶点k时，所有仅使用顶点0到k-1的最短路径都已计算完成。
算法结束时，所有最短路径都被最优计算，因为每个可能的中间顶点都被考虑过。

为什么弗洛伊德-沃歇尔算法更适合密集图，而稀疏图则不然？
稠密图：边数远多于顶点数的图。
稀疏图：边数极少的图。

无论图中有多少条边，Floyd Warshall 算法运行的 O（V）3因此它最适合稠密图。对于稀疏图，约翰逊算法更为适用。

逐步实现

首先，将每个顶点视为所有顶点对之间的可能中间节点，更新距离矩阵。
逐个遍历每个顶点。对于每个选中的顶点，尝试改进通过该顶点的最短路径。k
当我们选择顶点数 k 作为中间顶点时，我们已经将顶点 {0， 1， 2， .. k-1} 视为中间顶点。
对于源顶点和目的顶点的每一对（i， j），有两种可能的情况。
k 不是从 i 到 j 的最短路径中的中间顶点。我们保持 dist[i][j] 的值不变。
k 是从 i 到 j 的最短路径中的中间顶点。如果 dist[i][j] > dist[i][k] + dist[k][j] 的值更新为 dist[i][k] + dist[k][j]
对每个顶点重复此过程 ，直到考虑所有中间可能性。k

import java.util.*; class GfG { // Solves the all-pairs shortest path // problem using Floyd Warshall algorithm static void floydWarshall(int[][] dist){ int V = dist.length; // Add all vertices one by one to // the set of intermediate vertices. for (int k = 0; k < V; k++) { // Pick all vertices as source one by one for (int i = 0; i < V; i++) { // Pick all vertices as destination // for the above picked source for (int j = 0; j < V; j++) { // shortest path from // i to j if(dist[i][k] != 1e8 && dist[k][j]!= 1e8) dist[i][j] = Math.min(dist[i][j],dist[i][k] + dist[k][j]); } } } } public static void main(String[] args) { int INF = 100000000; int[][] dist = { { 0, 4, INF, 5, INF }, { INF, 0, 1, INF, 6 }, { 2, INF, 0, 3, INF }, { INF, INF, 1, 0, 2 }, { 1, INF, INF, 4, 0 } }; floydWarshall(dist); for (int i = 0; i < dist.length; i++) { for (int j = 0; j < dist.length; j++) { System.out.print(dist[i][j] + " "); } System.out.println(); } } }

输出
0 4 5 5 7
3 0 1 4 6
2 6 0 3 5
3 7 1 0 2
1 5 5 4 0
时间复杂度：O（V3），其中V是图中的顶点数，我们运行三个大小为V的嵌套循环。
辅助空间：O（1）。

点击这里了解详细分析：弗洛伊德·沃沙尔算法的复杂度分析

注意：上述程序只打印最短距离。我们也可以通过将前驱信息存储在单独的二维矩阵中来修改解法，打印最短路径。

弗洛伊德-沃歇尔算法的实际应用
在计算机网络中，该算法可用于寻找网络中所有节点对之间的最短路径。这被称为网络路由。
航空业中，航班连接性旨在寻找机场之间的最短航线。
地理信息系统（GIS）应用通常涉及分析空间数据，如道路网络，以寻找地点之间的最短路径。
Kleene算法是Floyd Warshall的推广，可用于为正则语言寻找正则表达式。

编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548