本来想问一下姓艾名哎的“入”迪杰斯特拉算法（AC君爆肝ING），结果……
我看不懂了，各位大佬看吧QAQ
迪杰斯特拉算法：从原理到 C++ 实战，掌握单源最短路径求解
迪杰斯特拉（Dijkstra）算法是图论领域解决单源最短路径问题的经典贪心算法，由荷兰计算机科学家艾兹赫尔・迪杰斯特拉于 1956 年提出。该算法适用于带非负权边的有向 / 无向图，能高效求解从单个起点到所有其他顶点的最短路径，广泛应用于地图导航、网络路由规划、资源调度等场景。本文将从核心原理出发，结合 C++ 代码实现，全方位讲解迪杰斯特拉算法。
一、算法核心原理
迪杰斯特拉算法的核心是 “贪心策略 + 松弛操作”，通过逐步锁定起点到各顶点的最短路径，最终得到全局最优解。具体步骤如下：1. 初始化定义距离数组dist[]，dist[v]表示起点到顶点v的当前最短距离，初始时起点dist[start] = 0，其余顶点dist[v] = ∞（无穷大）。定义布尔数组visited[]，标记顶点是否已确定最短路径，初始时所有顶点visited[v] = false。使用优先队列（小根堆）存储待处理的顶点（以 “当前最短距离 - 顶点编号” 的形式），初始时将起点(0, start)入队。2. 贪心选择每次从优先队列中取出当前距离起点最近的顶点
u（小根堆顶元素），若u已确定最短路径（visited[u] = true），则跳过；否则标记u为已确定（visited[u] = true）。3. 松弛操作遍历顶点u的所有邻接顶点v，计算 “起点→u→v” 的路径长度（dist[u] + weight(u, v)）。若该长度小于dist[v]，则更新dist[v]为该值，并将(dist[v], v)入队（即使v已入队，重复入队不影响，后续处理时会跳过已确定的顶点）。4. 终止条件当优先队列为空时，所有顶点的最短路径均已确定，算法结束。
二、算法关键特性权值限制：
必须保证所有边的权重非负，否则松弛操作无法保证后续不会出现更短路径（负权边场景需使用贝尔曼 - 福特算法或 SPFA 算法）。时间复杂度：邻接矩阵存储图：(O(n^2))（n为顶点数），每次遍历所有未确定顶点。邻接表 + 优先队列（二叉堆）：(O((n+e)logn))（e为边数），每个顶点和边最多处理一次，堆操作耗时logn。适用场景：单源最短路径（单个起点，多终点），支持有向图和无向图（无向图可视为双向有向图）。
三、C++ 代码实现（邻接表 + 优先队列版）
1. 代码框架采用邻接表存储图（空间效率更高，适合稀疏图），优先队列使用 C++ STL 的priority_queue（默认大根堆，需自定义比较规则改为小根堆）。
2. 代码说明
数据结构：
Edge结构体：存储邻接顶点和边的权重，用于构建邻接表。
PII（pair<int, int>）：优先队列的元素类型，第一个值为当前最短距离，第二个值为顶点编号。
邻接表adj[]：adj[u]存储顶点u的所有出边。
核心函数dijkstra()：
初始化距离数组和标记数组，将起点入队。
循环取出优先队列的堆顶元素，跳过已确定的顶点，遍历邻接边执行松弛操作。
松弛操作中，若更新了顶点v的最短距离，则将新的距离和顶点入队。
主函数：
读取输入（顶点数、边数、起点，以及各条边的信息）。
调用dijkstra()算法，输出起点到所有顶点的最短距离。
3. 测试用例
输入示例（有向图）：
顶点说明：顶点 1 为起点，边 1→2（权重 2）、1→3（权重 5）、2→3（权重 1）、2→4（权重 3）、3→4（权重 2）。
输出结果：
结果分析：起点 1 到顶点 2 的最短距离为 2（1→2）。起点 1 到顶点 3 的最短距离为 3（1→2→3）。起点 1 到顶点 4 的最短距离为 5（1→2→4 或 1→2→3→4）。
四、常见误区与注意事项负权边问题：
迪杰斯特拉算法无法处理负权边。例如，若存在边 3→2（权重 - 5），则算法会错误地认为顶点 3 的最短距离为 5，而实际 1→3→2 的距离为 0，导致结果偏差。优先队列重复元素：优先队列中可能存在同一顶点的多个距离记录，无需额外删除旧记录，只需在取出时判断visited[u]，跳过已确定的顶点即可（重复记录不影响最终结果，仅增加少量堆操作）。顶点编号范围：代码中顶点编号从 1 开始（符合常规输入习惯），若需从 0 开始，只需调整main函数中的输入和输出循环。无穷大取值：代码中使用INT_MAX（int类型的最大值）表示无穷大，需注意路径长度溢出问题（若边权较大，可改用long
long类型存储距离）。
五、扩展优化斐波那契堆优化：
理论上可将时间复杂度降至(O(nlogn + e))，但斐波那契堆实现复杂，实际工程中极少使用。双向迪杰斯特拉：同时从起点和终点出发执行贪心策略，相遇时停止，可减少堆操作次数，适合求解两点间的最短路径。处理无向图：只需在添加边时，同时添加u→v和v→u两条边（代码中注释部分）。
总结
迪杰斯特拉算法是单源最短路径问题的核心解法，其贪心策略保证了在非负权边场景下的正确性和高效性。本文通过原理讲解、C++ 代码实现和测试用例，完整呈现了算法的应用过程。掌握该算法不仅能解决图论基础问题，也能为复杂场景（如带约束的路径规划）提供思路。在实际开发中，需根据图的稀疏程度选择邻接矩阵或邻接表存储，并注意避开负权边、重复入队等常见误区。
