Floyd-Warshall算法详解（C#实现多源最短路径）

算法核心思想

Floyd-Warshall采用动态规划的思想。它通过逐步引入中间顶点k，尝试优化从i到j的路径：如果从i到k再到j的距离比当前已知的i到j的距离更短，就更新这个距离。

状态转移方程如下：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

C#实现Floyd-Warshall算法

下面是一个完整的C#控制台程序，演示如何使用Floyd-Warshall算法计算多源最短路径。

using System;namespace FloydWarshallDemo{    class Program    {        const int INF = int.MaxValue / 2; // 避免溢出        static void Main(string[] args)        {            // 示例图：4个顶点            int[,] graph = {                {0,   3,   INF, 7},                {8,   0,   2,   INF},                {5,   INF, 0,   1},                {2,   INF, INF, 0}            };            FloydWarshall(graph);        }        static void FloydWarshall(int[,] graph)        {            int n = graph.GetLength(0);            int[,] dist = new int[n, 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++)                    {                        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];                        }                    }                }            }            // 输出结果            Console.WriteLine("所有顶点对之间的最短距离：");            for (int i = 0; i < n; i++)            {                for (int j = 0; j < n; j++)                {                    if (dist[i, j] == INF)                        Console.Write("INF\t");                    else                        Console.Write(dist[i, j] + "\t");                }                Console.WriteLine();            }        }    }}

关键点说明

• INF 的设定：为了避免加法溢出，我们通常将无穷大设为 int.MaxValue / 2 而不是 int.MaxValue。
• 时间复杂度：Floyd-Warshall的时间复杂度为 O(n³)，适用于顶点数不太大的图（一般 n ≤ 500）。
• 空间复杂度：O(n²)，用于存储距离矩阵。
• 该算法还能检测图中是否存在负权环（如果某个 dist[i][i] < 0，则存在负环）。

应用场景

Floyd-Warshall算法广泛应用于网络路由、交通规划、社交网络分析等领域。当你需要频繁查询任意两点间的最短路径时，预计算一次Floyd-Warshall的结果会非常高效。

总结

通过本文，你已经掌握了Floyd-Warshall算法的基本原理及其在C#中的多源最短路径实现。作为图论算法中的重要工具，它不仅能帮助你解决复杂的路径问题，还能加深你对动态规划的理解。希望你能将所学应用到实际项目中！

关键词回顾：Floyd-Warshall算法、C#多源最短路径、图论算法、最短路径C#实现。