边权仅取两个值的有向图O(V+E)时间最短路径求解方法问询

我们默认讨论边权非负的通用场景，若存在负权且无负权环的情况可以参考文末的扩展方案。

预处理步骤 #

• 先统一两种权值的大小关系，不妨设x < y，如果实际x大于y直接交换两者命名即可。
• 边界情况：如果x = y，说明所有边权值相等，直接用普通BFS遍历即可得到所有节点的最短距离，复杂度天然满足O(V+E)。

核心算法（双端队列BFS） #

这是0-1 BFS的通用扩展版本，逻辑完全适配边权仅为两种固定值的场景：

1. 初始化距离数组dist，所有节点的初始值设为无穷大，源点对应的距离设为0。
2. 初始化一个双端队列deque，将源点加入队列。
3. 循环处理队列直到队列为空：
   • 取出队首节点u
   • 遍历u的所有出边u→v，对应边权为w：
     • 如果dist[v] > dist[u] + w，更新dist[v] = dist[u] + w
     • 若当前边权为较小值x，将v插入到队列队首
     • 若当前边权为较大值y，将v插入到队列队尾

复杂度与正确性说明 #

该算法本质是Dijkstra的轻量化实现，完全符合贪心逻辑：由于边权只有两种取值，走小权值边得到的新节点距离一定比走大权值边得到的距离优先级更高，不需要额外的优先队列维护排序，仅用双端队列就能实现优先级调度。每个节点最多入队2次，所有边仅遍历一次，整体时间复杂度严格为O(V+E)。

负权场景扩展 #

如果两种权值包含负数且图中不存在负权环，可以用简化版的Dial算法：仅维护两个桶分别对应两种权值更新后的节点，按顺序处理桶内节点，复杂度依然可以保持O(V+E)。

内容的提问来源于stack exchange，提问作者Johnny