图最短路评测：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 distDijkstra 的不变量是每次从堆里弹出的最小距离节点在非负边权条件下已经确定最短。负权会破坏这个不变量。代码里的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((VE)logV)邻接矩阵写法可能是 O(V²)。点边规模不同最优实现也不同。最后题解要说明为什么算法适用。比起背出模板能说清非负边权、不变量和复杂度更能证明理解到位。五、总结图最短路评测要先判断边权、规模、查询类型和输出要求再选择 Dijkstra、Bellman-Ford 或 Floyd。Dijkstra 对了不代表场景对了。算法模板之前先检查它的前提条件。