Microsoft 从 0 到所有点最短距离：单位权 BFS 到带权 Dijkstra

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练图无向，可有多条边和零权边，带权版所有权重非负；单位权版每边权重恰 1。
• 顶点编号 0..n−1，返回按编号排列的最短距离；不可达返回 None。
• 若改成有向图，只去掉反向邻接边即可；若有负权边，Dijkstra 不成立，应按题目约束选 Bellman-Ford 等算法。

解题路线

1. 单位权时，从 0 做 BFS，第一次到达任一顶点的层数就是最少边数，也就是最短距离；队列保证逐层扩展。
2. 改为非负带权后，最少边数不等于最小权重和。用最小堆按当前候选距离取节点，对每条边做松弛，跳过已过期堆项。
3. Dijkstra 正确性依赖非负权：堆中最小距离节点被取出时，任何绕道尚未处理节点都不可能再降低它；零权仍可用。
4. 题目只说‘非 1’没有明示非负，面试时必须问负权/零权、有向性和不可达口径；不能直接把 Dijkstra 当无条件 follow-up 答案。

手动走一遍

边 0–1 权 10、0–2 权 1、2–1 权 1。单位权图从 0 到 1 直接一条边是最短；带权后绕 2 的代价 2 小于直接代价 10。若 3 是孤点，训练版输出 None。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Distances from vertex zero in nonnegative weighted or unit-edge graphs."""

from collections import deque
import heapq


def distances_from_zero(n: int, edges: list[tuple[int, int, int]], weighted: bool = False) -> list[int | None]:
    if n <= 0:
        raise ValueError("at least vertex zero required")
    graph = [[] for _ in range(n)]
    for source, target, weight in edges:
        if not 0 <= source < n or not 0 <= target < n:
            raise ValueError("vertex outside graph")
        if weight < 0 or (not weighted and weight != 1):
            raise ValueError("nonnegative weighted edges or unit unweighted edges required")
        graph[source].append((target, weight))
        graph[target].append((source, weight))  # Training contract: undirected.

    distance: list[int | None] = [None] * n
    distance[0] = 0
    if not weighted:
        queue = deque([0])
        while queue:
            node = queue.popleft()
            for neighbor, _ in graph[node]:
                if distance[neighbor] is None:
                    distance[neighbor] = distance[node] + 1
                    queue.append(neighbor)
        return distance

    heap = [(0, 0)]
    while heap:
        current, node = heapq.heappop(heap)
        if distance[node] != current:
            continue
        for neighbor, weight in graph[node]:
            candidate = current + weight
            if distance[neighbor] is None or candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))
    return distance

复杂度

n 点 m 边：单位权 BFS O(n+m) 时间与空间；允许重边且堆里保留旧候选的本实现上界 O((n+m) log(n+m)) 时间、O(n+m) 存储。

易错点与追问

容易失分的边界

• 边权变为非 1 后仍只比较 BFS 层数。
• 有负权边却使用 Dijkstra 并声称正确。
• 题目未说明无向图，却不声明训练版的反向边假设。
• 不可达点留为巨大 sentinel 后当正常距离输出。

继续深挖

• 若边权只为 0 或 1，如何用双端队列做 0-1 BFS？
• 若有负权但无负环，Bellman-Ford 的成本是多少？
• 若频繁查询不同起点，是否值得预处理全源最短路？