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

Question

我正在寻找一种方法来增强在无权有向图中使用的BFS方法，以在O(N+M)的时间内解决上述问题。其中N是顶点数，M是边数。

我考虑了以下几种方法：

1. 缩小那些之间存在0权重边的图的顶点。但这肯定是错误的，因为这样会改变图的属性并向原本没有边的顶点添加新的边。

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

更普遍地说，当边的权重在0和MAX之间时，如何在线性时间内找到有向图中的单源最短路径。（MAX是最大边权）

- Nikunj Banka

---

顺便提一下，在使用二进制堆作为优先队列的情况下，通常情况下你会得到O((n + m) log n)的时间复杂度。如果MAX非常小，你可以使用桶和y-fast trie来实现优先队列，这将导致空间复杂度为O(n)，时间复杂度为O((n + m) * log log (n * MAX))（不知道在实践中速度有多快，但我真的很想知道:D）。 - Niklas B.

Torben Hagerup 在《在 Word RAM 上改进最短路径算法》一文中的解释可能对您有所帮助。 - SpaceTrucker

如果你只有MAX个不同的长度，那么你可以为每个距离的顶点建立一个队列。基本上，你正在创建一个常数时间优先级队列。 - Thomas Ahle

Answer 1

您可以使用带有一些修改的bfs：维护一个双端队列而不是一个队列，并且如果使用0条边，则将顶点添加到deque的前面，否则将其添加到deque的后面。（我现在指的是0-1情况）

- kraskevich

---

请您详细说明一下您的方法。您从哪里弹出/移除双端队列中的元素，以及您如何运行算法？如果我没错的话，您正在尝试维护2个队列，但是算法仍然不清楚。 - Nikunj Banka

从前面弹出。其他都和通常的BFS一样。 - kraskevich

相当不错的方法。实现起来也非常简单。我非常喜欢这个，这是一个常见的做法吗？ - Niklas B.

这真的很酷！实际上，这只是 Dijkstra 算法，我们注意到权重为 0 的边总是会排在优先队列的前面。 - Thomas Ahle

Answer 2

我认为你可以通过顶点收缩来解决这个问题。这里有一个提示：

首先，将由0权重边连接的顶点形成连通分量，并选择每个连通分量中的一个代表成员。这将给你一个收缩后的图。

然后解决无权问题。

真正的路径将由“内部边”（权重为1）连接代表成员和“内部边”组成，从传入的内部边到传出的内部边连接组件内的顶点。换句话说，你需要能够找到从任何代表到任何其他代表的路径。

- user1196549

---

你的算法在以下情况下会失败。请查看此链接http://pastebin.com/qzYFJLz0 - Nikunj Banka

没错。有向性很重要，因为在同一组件中无法从任何一个顶点到达另一个顶点。我忽视了这一点。 - user1196549