所有最短路径上出现的节点：两遍BFS距离等式

题目重点：无需枚举指数多条最短路径，逐节点检查距离相加。

题意与假设

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

无向无权图，节点0..n−1；只返回属于至少一条S→T最短路径的节点集合。
Bob同时追捕的follow-up未给速度、等待、边相遇与捕获规则，留待核，本文不以距离大小猜结论。

解题路线

从S和T各BFS得dS/dT。最短总长L=dS[T]，若不可达返回空。
v在某条最短路上当且仅当dS[v]+dT[v]=L。必要性来自最短路两段；充分性拼接最短两段，若出现可删正长循环便会小于L，矛盾。
边同理：dS[u]+1+dT[v]=L或反向式成立。按dS层构建最短路径DAG后可继续计路、找必经点或做明确时间模型的分析。

手动走一遍

菱形S→A/B→T，L2，S/A/B/T均满足等式；旁支X若到S一边不通T，则不在最短路径上。S=T时L0，仅S满足，尽管其邻居也可返回S形成更长环。

Python 参考实现

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

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

from collections import deque


def shortest_nodes(n,edges,start,end):
    if not 0<=start<n or not 0<=end<n:
        raise ValueError("invalid vertex")
    graph=[set() for _ in range(n)]
    for u,v in edges:
        if not 0<=u<n or not 0<=v<n:
            raise ValueError("invalid edge")
        graph[u].add(v);graph[v].add(u)
    def bfs(s):
        d=[None]*n;d[s]=0;q=deque([s])
        while q:
            u=q.popleft()
            for v in graph[u]:
                if d[v] is None:d[v]=d[u]+1;q.append(v)
        return d
    a,b=bfs(start),bfs(end)
    if a[end] is None:return []
    return [v for v in range(n) if a[v] is not None and b[v] is not None and a[v]+b[v]==a[end]]

复杂度

O(V+E)时间和O(V+E)空间含图与两距离数组；结果O(V)。枚举实际路径可能指数多。

易错点与追问

容易失分的边界

只保存第一次BFS parent会丢掉其他最短路径。
有向图从T要遍历反向边，不能原图BFS照搬。

继续深挖

怎样判断节点位于每一条最短路径，计数大数/模数碰撞要如何避免？
Bob移动允许等待或边上相遇时，应怎样建时间扩展状态？