Dijkstra算法详解（C#实现最短路径问题的完整教程）

Dijkstra 算法的基本思想

算法的核心思想是“贪心”策略：

1. 维护一个集合，记录已经确定最短路径的顶点。
2. 从起点开始，初始化所有顶点的距离为无穷大（∞），起点距离为0。
3. 每次从未确定最短路径的顶点中，选择当前距离最小的顶点，将其加入已确定集合。
4. 更新该顶点所有邻接顶点的距离（如果通过当前顶点到达邻接点更短，则更新）。
5. 重复步骤3-4，直到所有顶点都被处理。

C# 实现 Dijkstra 算法

下面我们使用 C# 编写一个完整的 Dijkstra 算法实现。我们将使用邻接表来表示图，并借助优先队列（最小堆）来高效地选取当前距离最小的顶点。

using System;using System.Collections.Generic;class Program{    // 定义图的结构：邻接表    static Dictionary<int, List<(int to, int weight)>> graph =         new Dictionary<int, List<(int, int)>>();    static void Main(string[] args)    {        // 构建示例图（5个顶点，编号0~4）        for (int i = 0; i < 5; i++)            graph[i] = new List<(int, int)>();        // 添加边（有向图）        AddEdge(0, 1, 10);        AddEdge(0, 4, 5);        AddEdge(1, 2, 1);        AddEdge(1, 4, 2);        AddEdge(2, 3, 4);        AddEdge(3, 2, 6);        AddEdge(4, 1, 3);        AddEdge(4, 2, 9);        AddEdge(4, 3, 2);        int source = 0; // 起点        var distances = Dijkstra(source, 5); // 5个顶点        Console.WriteLine($"从顶点 {source} 到各顶点的最短距离：");        for (int i = 0; i < distances.Length; i++)        {            Console.WriteLine($"顶点 {i}: {distances[i]}");        }    }    static void AddEdge(int from, int to, int weight)    {        graph[from].Add((to, weight));    }    static int[] Dijkstra(int source, int vertexCount)    {        // 初始化距离数组        int[] dist = new int[vertexCount];        bool[] visited = new bool[vertexCount];        for (int i = 0; i < vertexCount; i++)            dist[i] = int.MaxValue;        dist[source] = 0;        // 使用优先队列（最小堆）存储 (distance, vertex)        var pq = new SortedSet<(int distance, int vertex)>(            Comparer<(int, int)>.Create((a, b) => a.distance != b.distance ? a.distance.CompareTo(b.distance) : a.vertex.CompareTo(b.vertex))        );        pq.Add((0, source));        while (pq.Count > 0)        {            var current = pq.Min;            pq.Remove(current);            int u = current.vertex;            if (visited[u]) continue;            visited[u] = true;            // 遍历所有邻接点            foreach (var edge in graph[u])            {                int v = edge.to;                int weight = edge.weight;                if (!visited[v] && dist[u] != int.MaxValue &&                    dist[u] + weight < dist[v])                {                    dist[v] = dist[u] + weight;                    pq.Add((dist[v], v));                }            }        }        return dist;    }}

代码说明

• 图的表示：我们使用 Dictionary<int, List<(int, int)>> 来表示邻接表，每个顶点对应一个邻接点列表，每个邻接点包含目标顶点和边的权重。
• 优先队列：虽然 C# 没有内置的优先队列，但我们用 SortedSet 模拟最小堆，按距离排序。
• 避免重复处理：使用 visited 数组确保每个顶点只被处理一次。
• 距离更新：当发现更短路径时，更新距离并加入队列。

运行结果示例

对于上述图，从顶点 0 出发，输出结果为：

从顶点 0 到各顶点的最短距离：顶点 0: 0顶点 1: 8顶点 2: 9顶点 3: 7顶点 4: 5

总结

通过本教程，你已经掌握了如何在 C# 中实现 Dijkstra算法，并理解了其背后的贪心思想。该算法是解决单源最短路径问题的基石，也是学习更复杂图论算法（如 A*、Floyd-Warshall）的重要基础。

记住：Dijkstra 算法适用于非负权重的图。如果图中存在负权边，请考虑使用 Bellman-Ford 算法。

希望这篇关于 C#最短路径 的教程对你有所帮助！动手试试修改图的结构，观察最短路径的变化吧。