C# 路径算法之Floyd-Warshall算法

Floyd-Warshall 算法是一种计算图中所有最短路径的动态规划算法。它可以处理包括正权值、负权值（但不能处理负权环）的图。该算法可以计算出图中任意两个顶点之间的最短路径。

在 C# 中实现 Floyd-Warshall 算法，我们需要一个二维数组（或二维列表）来存储图中各顶点之间的直接距离（如果两个顶点之间没有直接连接，则使用一个足够大的数，如 int.MaxValue，来表示无穷大）。然后，我们使用三层嵌套循环来更新这个距离矩阵，最终得到所有顶点对之间的最短路径。

以下是 Floyd-Warshall 算法的一个 C# 实现示例：

using System;class FloydWarshall
{static void Main(string[] args){// 示例图的邻接矩阵表示// 假设顶点编号为 0 到 4int[,] graph = new int[,]{{ 0, 5, inf, 10, inf },{ inf, 0, 3, inf, 8 },{ inf, inf, 0, inf, 2 },{ inf, 1, 7, 0, 4 },{ inf, inf, inf, inf, 0 }};const int inf = int.MaxValue; // 用来表示无穷大int V = graph.GetLength(0); // 顶点的数量// Floyd-Warshall 算法for (int k = 0; k < V; k++){for (int i = 0; i < V; i++){for (int j = 0; j < V; j++){// 更新最短路径if (graph[i, k] + graph[k, j] < graph[i, j]){graph[i, j] = graph[i, k] + graph[k, j];}}}}// 打印结果Console.WriteLine("以下是所有顶点对之间的最短路径长度：");for (int i = 0; i < V; i++){for (int j = 0; j < V; j++){if (graph[i, j] == inf){Console.Write("INF ");}else{Console.Write(graph[i, j] + "   ");}}Console.WriteLine();}}
}

注意：

1. 在这个示例中，我使用了一个二维数组 graph 来存储图的邻接矩阵。如果两个顶点之间没有直接连接，则对应的矩阵元素被设置为 inf（这里定义为 int.MaxValue）。

2. Floyd-Warshall 算法的核心是三重循环，其中 k 作为中间顶点，i 和 j 分别表示起始和结束顶点。对于每一对 (i, j)，算法检查是否可以通过顶点 k 来找到更短的路径。

3. 算法的时间复杂度为 O(V^3)，其中 V 是图中顶点的数量。这使得它在处理大型图时可能不是很高效。

4. 输出的最短路径长度矩阵展示了图中所有顶点对之间的最短距离。如果两个顶点之间没有路径，则对应的值为 INF。