题干与适用场景
给定一张有向图，共有 n 个节点，编号为 0 到 n - 1。每条边用 (from, to, weight) 表示。给定 source 和 target，返回从起点到终点的最短距离和 任意一条最短路径；如果终点不可达，返回 (-1, [])。
本题约定 1 <= n <= 100000、0 <= m <= 300000，节点编号均合法，且 0 <= weight <= 10^9。允许平行边、零权边和自环；source、target 一定合法。 若起点就是终点，返回 (0, [source])。存在多条等长最短路径时，返回任意一条即可。
例如，边为 (0, 1, 4)、(0, 2, 1)、(2, 1, 2)、(1, 3, 1)、 (2, 3, 5)、(3, 4, 3)、(2, 4, 12) 时，从 0 到 4 的最短距离为 7， 路径为 [0, 2, 1, 3, 4]。
“边权非负”是算法合同的一部分。看到带权图不能立刻套 Dijkstra：无权或等权图优先 考虑 BFS；DAG 可以按拓扑序做动态规划；一般图若含负权边，则要考虑 Bellman-Ford 等算法。
面试官考察点
第一，看能否从输入合同选对算法。这里只有单源查询，且所有边权非负，所以适合 Dijkstra。只说“带权图用 Dijkstra”，却不确认负权边，是遗漏了最关键的前提。
第二，看能否把图和候选距离维护好。节点最多 100000 个，邻接矩阵需要 O(V^2) 空间， 不适合本题。邻接表只保存实际存在的边；最小堆负责取出当前已发现距离最小的未确定节点。
第三，看是否理解堆中的重复条目。Python 的 heapq 不支持直接修改任意条目的优先级。 常见做法是在距离变小时压入新条目，旧条目以后出堆时，如果距离已经不等于 distances[node]，就把它当作过期条目跳过。这个惰性删除细节会影响正确性说明和精确复杂度。
面试官还会追问证明：为什么节点的当前条目第一次出堆后距离就确定了；为什么非负边权能 保证这个贪心步骤；为什么可以在终点出堆时结束，却不能在第一次发现终点时结束。路径还原、 不可达、零权边、平行边、整数位宽和对抗测试也应主动覆盖。
回答前需要澄清的问题
- 边权可能为负吗？ 本题明确不会。若允许负权边，Dijkstra 的确定性证明和提前退出都不成立。
- 图是有向图吗？ 是。无向图需要把每条边的两个方向都加入邻接表。
- 只返回距离，还是也要返回路径？ 本题两者都要，所以每次严格改善距离时还要记录前驱。
- 允许平行边、零权边和自环吗？ 允许。松弛操作可直接处理；非负自环不会改善当前节点。
- 不可达如何表示？ 返回
(-1, [])，避免与起点等于终点的零距离混淆。 - 多条最短路径如何选？ 任意一条即可。实现只在严格变小时更新前驱，等长路径不会反复改写。
- 距离会不会溢出？ 简单最短路径至多包含
n - 1条边，在本题约束下小于10^14。
Python 整数不会溢出；定长整数语言应使用 64 位类型。
30 秒回答框架
“我会先建立邻接表，用 distances[v] 表示目前找到的起点到 v 的最短距离。起点距离设为 0，并把 (0, source) 放进最小堆。每次弹出最小条目，如果它与数组中的当前距离不一致， 说明已经过期，直接跳过；否则由于所有边权非负，这个节点的距离已经确定。接着松弛所有出边， 每次严格改善都压入新条目并记录前驱。终点的当前条目出堆时可以结束。若终点仍为无穷大，返回 (-1, [])；否则沿前驱逆向还原路径再翻转。惰性重复条目的实现时间为 O((V + E) log E)，空间为 O(V + E)。”
分步骤深入解答
先区分“找到一条路”和“已经证明最短”。distances[v] 要么是无穷大，要么是某条实际路径的 长度，因此它是最短距离的上界，不会凭空小于真实答案。对边 u -> v、边权 w 做松弛时， 判断经过 u 的路径是否更短：distances[u] + w < distances[v]。只有严格变小时才更新 距离和 previous[v]。
堆中允许同一节点出现多次。示例里，边 0 -> 1 会先压入距离 4；处理节点 2 后，路径 0 -> 2 -> 1 又把节点 1 改善为距离 3，并压入第二个条目。以后 (4, 1) 出堆时， 4 != distances[1]，说明它已经过期，应直接跳过。不需要在堆里查找并删除旧条目，也不需要 额外用一个在入堆时就标记的 visited 集合。
from heapq import heappop, heappush
def shortest_path(
n: int,
edges: list[tuple[int, int, int]],
source: int,
target: int,
) -> tuple[int, list[int]]:
graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for node, neighbor, weight in edges:
if weight < 0:
raise ValueError("Dijkstra requires non-negative edge weights")
graph[node].append((neighbor, weight))
distances = [float("inf")] * n
previous = [-1] * n
distances[source] = 0
heap: list[tuple[int, int]] = [(0, source)]
while heap:
distance, node = heappop(heap)
if distance != distances[node]:
continue
if node == target:
break
for neighbor, weight in graph[node]:
candidate = distance + weight
if candidate < distances[neighbor]:
distances[neighbor] = candidate
previous[neighbor] = node
heappush(heap, (candidate, neighbor))
if distances[target] == float("inf"):
return -1, []
path = []
node = target
while node != -1:
path.append(node)
node = previous[node]
path.reverse()
return int(distances[target]), path正确性可以分两步证明。第一，每个有限的 distances 值都来自一条实际已发现路径，所以不可能 低于真实最短距离。第二，假设节点 u 的当前条目出堆了，却还存在一条更短路径。在这条更短路径 上找到第一个尚未确定的节点，其前驱记为 x。x 已经更早确定，因此它的出边已经被松弛； 这个未确定节点会得到一个不大于那条假设路径长度的堆键。因为余下边权都非负，这个键严格小于 刚弹出的 u 的键，理应先出堆，产生矛盾。所以当前出堆距离一定已经是最短距离。
这个证明也确定了提前退出的位置：只能在终点以当前、未过期距离出堆后停止，不能在某条边第一次 发现终点时停止。示例中节点 4 最早被发现的直接候选距离是 13，最终最短距离却是 7。
每次 previous[v] = u 都记录了当前最优路径的最后一条边。终点距离确定后，沿前驱向回走一定 能到起点，因为每个前驱都来自一条真实的起点路径。逆序收集后再翻转即可得到正向路径。起点等于 终点时，起点第一次出堆就结束，还原结果自然是 [source]。
建立邻接表需要 O(E) 时间和 O(V + E) 空间。每次成功松弛最多新增一个堆条目，因此除起点 外最多有 E 次入堆。惰性重复条目会让堆规模达到 O(E)，所以时间为 O((V + E) log E)，总空间为 O(V + E)。教材中常见的 O((V + E) log V) 一般对应 支持 decrease-key 的堆，或对简单稀疏图做了常用简化；面试时说明实现差异更准确。
测试要覆盖合同，而不只是一条正常样例。上述样例应返回 (7, [0, 2, 1, 3, 4])。平行边和 零权边 (0, 1, 10)、(0, 1, 2)、(1, 2, 0) 应返回 (2, [0, 1, 2])。 还要测试终点不可达、起终点相同、自环、等长候选路径和零权边。负权边应触发明确异常，不能在算法 前提已破坏时悄悄返回一个结果。
还可以做小规模差分测试：随机生成非负权图，对每个起点分别运行本函数和 Bellman-Ford，比较所有 距离。对返回路径，还要检查首尾节点、每一对相邻节点是否有对应输入边，并累加所选边权。存在平行边 时，测试不能假定一对节点之间只有一条边，必须匹配实际采用的边权。
高质量示范回答
“我先确认所有边权非负、图是有向图，并且任意一条最短路径都可以返回。满足这些条件后可以使用 Dijkstra。节点最多 100000 个、边最多 300000 条，所以我会用邻接表；邻接矩阵空间太大。
distances[v] 初始都是无穷大，只有起点为 0。最小堆保存已经发现的 (distance, node)。 找到一条更短路径时，我更新邻居的距离和前驱，并压入新条目。由于 heapq 没有任意条目的 decrease-key，旧条目会留在堆中；出堆距离若不等于数组当前值，就说明过期，直接跳过。
核心是确定性不变量：当节点 u 的当前条目是堆顶时，任何假设中的更短路径都会包含一个首个尚未 确定的节点，它的前驱已经确定并完成松弛。由于余下边权非负，那个路径前缀对应的堆键应该早于 u 出堆，矛盾。因此 u 的距离已经最终确定。这也说明可以在终点的当前条目出堆时结束，但不能 在第一次看到终点时结束。
若终点仍是无穷大，我返回 (-1, [])；否则从终点沿前驱走回起点，再翻转得到路径。每次成功松弛 最多产生一个新堆条目，所以惰性实现的时间是 O((V + E) log E)，空间是 O(V + E)。 定长整数语言使用 64 位距离。我会测试过期条目、平行边、零权边、等长路径、起终点相同、不可达， 以及负权边被拒绝的情况。”
常见错误
- 不确认负权边就运行 Dijkstra → 贪心确定性证明失效 → 把非负边权写成明确前提，并拒绝非法输入。
- 第一次松弛到终点就退出 → 最早发现的路径可能很贵 → 只在终点的当前条目出堆时退出。
- 不跳过堆中过期条目 → 旧距离会重复扫描出边 → 检查
distance != distances[node]。 - 节点第一次入堆就标记访问 → 后续更短路径无法更新 → 只有当前最小条目出堆才算确定。
- 使用邻接矩阵 → 稀疏图也占用
O(V^2)内存 → 用O(V + E)的邻接表。 - 等长距离也更新前驱，却没有平局规则 → 零权环会让路径选择反复变化 → 任意最短路径场景只处理严格改善。
- 题目要求路径却只保留距离 → 无法完成返回合同 → 每次严格改善时记录前驱，搜索后还原。
- 不加说明就声称堆实现是
O(E log V)→ 惰性重复条目可能让堆规模达到E→
写出 O((V + E) log E)，再解释常见 decrease-key 界。
- 用 32 位整数存距离 → 路径长度可能远超约 21 亿 → 使用 Python 整数或 64 位类型。
- 测试只检查最终距离 → 错误的前驱链不会暴露 → 同时检查路径端点、边和总权重。
追问及应对
追问 1：如果只需要最短距离呢？
删除 previous 数组和路径还原即可。搜索流程、证明和渐进复杂度不变，只是少了一个 O(V) 的 节点数组。终点当前条目出堆时依然可以提前结束。
追问 2：如果要查询每个起点到所有节点的距离呢？
对每个节点运行一次本实现，代价为 O(V(V + E) log E)。稠密图可考虑 Floyd-Warshall， 时间 O(V^3)、空间 O(V^2)，并能处理无负环时的负权边。稀疏图若有负权边但没有负环， 可考虑通过重赋权后重复运行 Dijkstra 的 Johnson 算法。选择要基于图密度和查询量。
追问 3：如果允许负权边呢？
一般有向图使用 Bellman-Ford。它反复松弛所有边，时间为 O(VE)；额外一轮仍能成功松弛， 说明存在起点可达的负环。反例 0 -> 1 = 2、0 -> 2 = 5、2 -> 1 = -10 中， 提前退出的 Dijkstra 会把终点 1 确定为 2，但经过节点 2 的真实最短距离为 -5。
追问 4：如果图是 DAG，但边权可能为负呢？
先做拓扑排序，再按拓扑序把每条出边松弛一次。所有前驱一定先于后继处理，所以负权边也安全， 总时间为 O(V + E)。在更强的无环合同下，它比 Bellman-Ford 和 Dijkstra 都更合适。
追问 5：如果所有边权只有 0 或 1 呢？
使用双端队列做 0-1 BFS。零权边松弛后压到队首，权重 1 的边压到队尾；队列会维持距离非递减 顺序，不需要堆，时间降为 O(V + E)。
追问 6：如果边会频繁更新呢？
更新不频繁时，修改对应边后重新运行 Dijkstra 最容易验证。若更新频繁且延迟要求严格，才考虑 动态最短路或缓存单源最短路树并做失效处理；是否值得取决于更新与查询比例、图结构和规模。不能假设 一条边变化只影响它的两个端点。
追问 7：如何返回字典序最小的最短路径？
只用严格距离比较无法完成，因为它会保留第一条等长路径。先明确字典序合同。一种方案是先求最短 距离，再把候选转移限制为满足最短距离等式的边，之后在确保仍能到达终点的前提下选择最小下一节点。 零权环需要额外防环处理。小规模输入也可把完整路径元组放入堆中比较，但复制和比较成本可能很高。