C#最短路径的路径还原（从零开始掌握Dijkstra算法与路径追踪）

核心思路：记录前驱节点

要实现Dijkstra路径还原，关键在于在松弛（Relaxation）过程中记录每个节点的“前驱节点”（Predecessor）。当我们找到一条更短的路径到达某个节点时，就更新它的前驱为当前节点。最后，从终点反向回溯到起点，即可得到完整路径。

C#代码实现

下面是一个完整的C#控制台程序示例，展示了如何使用Dijkstra算法计算最短路径并还原路径：

using System;using System.Collections.Generic;using System.Linq;class Program{    static void Main()    {        // 构建图：邻接表表示        var graph = new Dictionary<int, List<(int to, int weight)>>()        {            { 0, new List<(int, int)> { (1, 4), (2, 1) } },            { 1, new List<(int, int)> { (3, 1) } },            { 2, new List<(int, int)> { (1, 2), (3, 5) } },            { 3, new List<(int, int)>() }        };        int start = 0, end = 3;        var (distances, predecessors) = Dijkstra(graph, start);        Console.WriteLine($"从节点 {start} 到节点 {end} 的最短距离是: {distances[end]}");        if (distances[end] != int.MaxValue)        {            var path = ReconstructPath(predecessors, start, end);            Console.WriteLine($"最短路径为: {string.Join(" -> ", path)}");        }        else        {            Console.WriteLine("无法到达目标节点。");        }    }    static (Dictionary<int, int> distances,                Dictionary<int, int?> predecessors)         Dijkstra(Dictionary<int, List<(int, int)>> graph, int start)    {        var distances = new Dictionary<int, int>();        var predecessors = new Dictionary<int, int?>();        var pq = new SortedSet<(int distance, int node)>();        foreach (var node in graph.Keys)        {            distances[node] = node == start ? 0 : int.MaxValue;            predecessors[node] = null;        }        pq.Add((0, start));        while (pq.Count > 0)        {            var current = pq.Min;            pq.Remove(current);            int u = current.node;            int distU = current.distance;            if (distU > distances[u]) continue;            foreach (var (v, weight) in graph[u])            {                int newDist = distU + weight;                if (newDist < distances[v])                {                    pq.Remove((distances[v], v)); // 移除旧值（简化处理）                    distances[v] = newDist;                    predecessors[v] = u;                    pq.Add((newDist, v));                }            }        }        return (distances, predecessors);    }    static List<int> ReconstructPath(Dictionary<int, int?> predecessors,                                          int start, int end)    {        var path = new List<int>();        int? current = end;        while (current.HasValue)        {            path.Add(current.Value);            current = predecessors[current.Value];        }        path.Reverse();        return path[0] == start ? path : new List<int>();    }}  

代码详解

• 图的表示：使用字典存储邻接表，键是节点，值是（邻居节点, 边权重）的列表。
• Dijkstra函数：返回两个字典：distances（最短距离）和predecessors（前驱节点），这是实现C#路径追踪实现的关键。
• ReconstructPath函数：从终点开始，通过predecessors不断回溯，直到起点，最后反转列表得到正向路径。

运行结果

以上代码输出：

从节点 0 到节点 3 的最短距离是: 3最短路径为: 0 -> 2 -> 1 -> 3  

总结

通过本文，你已经掌握了在C#中实现图论编程教程中最实用的技术之一：最短路径的路径还原。记住，核心在于记录前驱节点，并通过回溯构建路径。这项技能不仅适用于学术研究，也广泛应用于游戏开发、物流系统、社交网络分析等领域。

现在，你可以尝试修改图结构或添加更多功能（如处理负权边用Bellman-Ford），进一步提升你的C#最短路径算法实战能力！