图最短路评测：Dijkstra 对了，也可能用错场景

图最短路评测：Dijkstra 对了，也可能用错场景

一、最短路算法不是只背名字

图论题里，最短路是高频考点。Dijkstra、Bellman-Ford、Floyd、SPFA 名字很多，但真正重要的是场景选择。边权是否为负、点数边数多大、是否多源多汇、是否需要路径恢复，都会影响算法选择。

Dijkstra 写对了，如果用在负权图上，答案仍然可能错。

二、先判断图条件

flowchart TD A[最短路问题] --> B{是否有负权} B -->|否| C[Dijkstra] B -->|是| D{是否有负环} D -->|无| E[Bellman-Ford] D -->|有| F[不存在稳定最短路] A --> G{是否全源} G --> H[Floyd 或多次单源]

算法选择前，先看边权、规模和查询次数。不要看到最短路就直接写 Dijkstra。

shortest_path_decision: non_negative_edges: dijkstra negative_edges_no_cycle: bellman_ford all_pairs_small_graph: floyd

选择依据写清楚，题解才完整。

三、Dijkstra 的关键不变量

import heapq def dijkstra(graph, start): 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.get(v, float("inf")): dist[v] = nd heapq.heappush(pq, (nd, v)) return dist

Dijkstra 的不变量是：每次从堆里弹出的最小距离节点，在非负边权条件下已经确定最短。负权会破坏这个不变量。

代码里的if d != dist[u]是为了跳过过期堆元素。Python 的堆不支持直接 decrease-key，所以会插入多份候选。

四、评测要覆盖错误场景

如果只用正权图测试，Dijkstra 写错场景也发现不了。评测集应该包含负权边、不可达点、多条等长路径、稠密图、稀疏图和大权值。

shortest_path_tests: unreachable_nodes: true negative_edge: true equal_distance_paths: true large_weight: true

还要测试路径恢复。如果题目要求输出路径，只返回距离不够。需要保存前驱节点，并在更新 dist 时同步更新 parent。

复杂度也要结合图表示。邻接表 + 堆的 Dijkstra 是 O((V+E)logV)，邻接矩阵写法可能是 O(V²)。点边规模不同，最优实现也不同。

最后，题解要说明为什么算法适用。比起背出模板，能说清非负边权、不变量和复杂度，更能证明理解到位。

五、总结

图最短路评测要先判断边权、规模、查询类型和输出要求，再选择 Dijkstra、Bellman-Ford 或 Floyd。

Dijkstra 对了不代表场景对了。算法模板之前，先检查它的前提条件。