弗洛伊德算法（Floyd’s algorithm），也被称为弗洛伊德-沃舍尔算法（Floyd-Warshall algorithm），是一种用于解决图中所有节点对之间最短路径的动态规划算法。
该算法可以在有向图或带权无向图中找到所有节点之间的最短路径。它的核心思想是通过所有中间节点逐步迭代来更新每对节点之间的最短路径。具体的步骤如下：
- 初始化一个矩阵，矩阵的每个元素代表从一个节点到另一个节点的最短路径长度。如果两个节点之间没有直接连接，那么路径长度为无穷大。对角线上的元素设置为0。
- 通过遍历图中的每一个中间节点（1到n），将中间节点作为路径中的一个中转点，更新所有节点对之间的最短路径长度。如果从节点i到节点j的路径通过中间节点k比当前路径更短，那么更新路径长度为更短的路径。
- 重复步骤2直到遍历完所有的中间节点，此时矩阵中的元素表示所有节点对之间的最短路径长度。
弗洛伊德算法的时间复杂度为O(n^3)，其中n是节点的数量。它可以很好地处理带有负权边的图，但是如果图中存在负权环，该算法将无法工作。
当使用弗洛伊德算法解决最短路径问题时，可以根据生成的最短路径矩阵来获取具体的最短路径。
一旦算法执行完成，得到的最短路径矩阵可以表示从任意节点到任意节点的最短路径长度。要获取两个节点之间的最短路径，可以按照以下步骤进行操作：
- 首先，检查矩阵中两个节点之间的距离是否为无穷大（表示没有路径可行）。如果是，那么表示这两个节点之间不存在可行路径。
- 如果两个节点之间的距离不是无穷大，那么可以通过观察路径矩阵来逐步推断最短路径。
- 设最短路径矩阵为D，节点i到节点j的最短路径长度为D[i][j]。
- 如果D[i][j]等于无穷大或者i等于j，那么表示节点i到节点j之间没有路径。
- 如果D[i][j]不等于无穷大，那么可以通过观察D矩阵的其他元素来推断路径的中间节点。
- 假设k是从i到j的最短路径上的一个中间节点，那么可以检查D[i][k] + D[k][j]是否等于D[i][j]。如果相等，那么可以推断出路径上包括了节点k。
- 通过迭代这个过程，可以根据D矩阵逐步推断出路径上的所有中间节点，从而得到最短路径。
这样，根据最短路径矩阵和推断路径的方法，就可以找到任意两个节点之间的最短路径。这对于网络规划、数据通信、物流运输等领域非常有用。
举例
#include <iostream> #include <vector> #include <climits> using namespace std; #define INF INT_MAX // 表示无穷大的值 void floydWarshall(vector<vector<int>>& graph) { int n = graph.size(); // 创建和初始化最短路径矩阵 vector<vector<int>> dist(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = graph[i][j]; } } // 通过中间节点逐步迭代更新最短路径 for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // 如果从节点i到节点j的路径通过中间节点k比当前路径更短，则更新路径长度 if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } // 打印最短路径矩阵 cout << "最短路径矩阵：" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][j] == INF) { cout << "INF "; } else { cout << dist[i][j] << " "; } } cout << endl; } } int main() { // 构建图的邻接矩阵表示 vector<vector<int>> graph = { {0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0} }; floydWarshall(graph); return 0; }
在上述示例中，我们首先定义了邻接矩阵表示的图。然后，通过调用floydWarshall函数，将图作为参数传递给弗洛伊德算法的实现。
算法会计算并输出最短路径矩阵，其中的值表示从一个节点到另一个节点的最短路径长度。无穷大的值(INF)表示节点之间不存在路径。
请注意，示例中定义的图是一个有向图，并且使用邻接矩阵表示。在实际应用中，你可以根据具体的需求和图的类型来自定义图的表示方式，并将其传递给弗洛伊德算法进行计算。
