Dijkstra 算法模板与思路
一、适用场景Dijkstra 用于求单源最短路，也就是从一个起点出发，到其他所有点的最短距离。 使用前提：所有边权非负。只要有负权边，Dijkstra 就可能出错，需要换 SPFA 或 Bellman-Ford。 二、核心思路Dijkstra 的本质是贪心。 维护一个数组 dist[]，dist[i] 表示从起点到点 i 的当前最短距离。初始时起点为 0，其余为无穷大。 每一轮做两件事： 从未确定的点中，取出 dist 最小的那个点 u，此时 dist[u] 就是起点到 u 的最终最短路。 用 u 去松弛它的所有邻居：如果 dist[v] > dist[u] + w(u,v)，就更新 dist[v]。 为什么取出的点可以直接确定？因为边权非负，后面再绕路不可能比现在更短。 三、复杂度 朴素实现：每轮 O(n) 找最小点，总共 O(n²)，适合稠密图。 优先队列优化：每轮 O(log n) 取最小点，总共 O(m log n)，适合稀疏图。其中 n 是点数，m 是边数。 四、优先队列优化模板#include<bits/stdc++.h> using name...