2

假设我们想在一个图上运行 Dijkstra 算法，该图的边权重是范围内的整数{1,2,...,W}，其中 W 是一个相对较小的数字。如何找到从顶点s到tin的最短路径O((|V|+|E|)logW)？

我在 S. Dasgupta、C. Papadimitriou 和 U. Vazirani 的《算法》一书中遇到了这个问题。我可以证明，如果我们像以前一样实现 Dijkstra 算法，在每次迭代中，优先级队列中节点的距离范围将在W. 然而，由于优先队列不具有将具有相同权重的元素放入同一个桶中的属性，因此这种观察并不能直接导致问题的解决方案。

谁能给我一些关于如何更进一步使有界范围W对我有用的提示？

谢谢！

4

1 回答 1

1

您的优先队列中可以有多少个不同的号码？

解决方案 请注意，在您提取大小为 X 的节点后（现在您放松了..），它可以达到的最大大小为 X+W。所有其他数字都比 X 大（因为你从队列中取了最小值）所以队列中只有 O(W) 个不同的数字，所以你可以将它用作二进制堆，然后每一步都需要 O(logW ) 加起来就是：(V+E)logW。

于 2014-01-23T14:30:44.217 回答