Dijkstra 入门优先队列里放的是当前最可信的距离Dijkstra 用来解决非负权图的单源最短路。很多人背代码时卡在优先队列其实优先队列里放的是“当前最可信的距离”。每次取出距离最小的点如果这个距离还没过期就用它去更新邻居。理解“过期距离”之后Dijkstra 的代码会顺很多。一、算法过程flowchart TD A[初始化源点距离为 0] -- B[源点入优先队列] B -- C[取出最小距离节点] C -- D{距离是否过期} D --|是| C D --|否| E[松弛邻边] E -- F[更新后入队] F -- C优先队列可能有同一个点的多个距离旧的较大距离就是过期数据。二、代码模板import heapq def dijkstra(n, graph, start): dist [float(inf)] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d ! dist[u]: continue for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return distif d ! dist[u]是过期判断。没有它也可能算对但会多做很多无用功。三、为什么不能有负权Dijkstra 的正确性依赖一个事实每次弹出的最小距离已经不会再变小。负权边会打破这个事实。后面绕一圈回来可能更短。有负权边时要考虑 Bellman-Ford 或 SPFA。别拿 Dijkstra 硬怼算法不是靠勇气运行的。四、复杂度使用优先队列时复杂度通常是 O((VE)logV)。稠密图和稀疏图表现不同面试时至少要能说明 V 是点数E 是边数。如果题目是网格最短路也可以把每个格子当成点。坐标到编号的映射要写清楚。还要注意“最短路状态”不一定只有节点。有些题里状态包含节点和剩余次数比如可以消除障碍、可以打折一次。此时 dist 可能是二维甚至三维。dist[node][used_coupon] best_cost把状态维度想清楚比硬套模板重要。模板只负责跑状态定义决定你跑的是不是正确问题。Dijkstra 的另一个边界是大数。距离初始化要足够大累加时注意溢出。Python 没这个烦恼其他语言要小心。如果图是稀疏图用邻接表如果是稠密图邻接矩阵也可以但复杂度会变。题目给的 n 和边数 m要先看清楚。别在十万条边的题里用矩阵把内存炸了。graph_choice: sparse: adjacency_list dense: adjacency_matrix_possible large_n: avoid O(n^2) memory图论题先看约束再选结构。结构选错算法再对也跑不动。面试表达里先说约束再说为什么选 Dijkstra会比直接背模板更像真正理解。五、总结Dijkstra 的优先队列里放的是当前最可信的距离。每次取最小、跳过过期、松弛邻边。它适合非负权图不适合负权边。会写模板还不够要知道它为什么能贪心地确认最短距离。