如何在线性时间内边缘权重为0或1的有向图中找到最短路径？

Question

我正在寻找一种方法来增加用于在未加权有向图中找到单源最短路径的BFS方法,并在O(N + M)时间内解决上述问题.其中N是顶点数,M是边数

我想到了以下几点:

1. 收缩图表的顶点,它们之间的边权重为0.但这绝对是错误的,因为我将更改图形的属性并向最初没有的顶点添加新边.

2. 将边权重更改为1和2.然后在长度为2的路径中创建虚拟顶点,将这些边转换为权重1的边.但这会给出错误的答案.

更一般地说,当边缘权重在线性时间内在0和MAX之间时,如何在有向图中找到单源最短路径.(MAX是最大边缘重量)

Answer 1

您可以使用bfs进行一些修改:维护deque而不是队列,如果使用0边,则在顶层的前面添加顶点,否则添加到deque的背面.(我的意思是0-1情况)