我正在寻找一种方法来增强在无权有向图中使用的BFS方法,以在O(N+M)的时间内解决上述问题。其中N是顶点数,M是边数。
我考虑了以下几种方法:
1. 缩小那些之间存在0权重边的图的顶点。但这肯定是错误的,因为这样会改变图的属性并向原本没有边的顶点添加新的边。
2. 将边的权重更改为1和2。然后在长度为2的路径中创建虚拟顶点,将这些边转换为权重为1的边。但这会得到错误的答案。
更普遍地说,当边的权重在0和MAX之间时,如何在线性时间内找到有向图中的单源最短路径。(MAX是最大边权)
我考虑了以下几种方法:
1. 缩小那些之间存在0权重边的图的顶点。但这肯定是错误的,因为这样会改变图的属性并向原本没有边的顶点添加新的边。
2. 将边的权重更改为1和2。然后在长度为2的路径中创建虚拟顶点,将这些边转换为权重为1的边。但这会得到错误的答案。
更普遍地说,当边的权重在0和MAX之间时,如何在线性时间内找到有向图中的单源最短路径。(MAX是最大边权)
O((n + m) log n)
的时间复杂度。如果MAX
非常小,你可以使用桶和y-fast trie来实现优先队列,这将导致空间复杂度为O(n)
,时间复杂度为O((n + m) * log log (n * MAX))
(不知道在实践中速度有多快,但我真的很想知道:D)。 - Niklas B.