作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
假设我们想在边权为整数的图上运行 Dijkstra 算法范围 {1,2,...,W}
,其中 W 是一个相对较小的数字。如何在O((|V|+|E|)logW)
中找到从顶点s
到t
的最短路径?
我在 S. Dasgupta、C. Papadimitriou 和 U. Vazirani 的《算法》一书中遇到了这个问题。我可以证明,如果我们像以前一样实现 Dijkstra 算法,在每次迭代中,优先级队列中节点的距离范围将在 W
范围内。但是,由于优先级队列不具有将相同权重的元素放入同一个桶中的特性,因此这种观察并不能直接导致问题的解决。
谁能给我一些提示,告诉我如何进一步使有界范围 W
为我工作?
谢谢!
最佳答案
您的优先队列中可以有多少个不同的号码?
解决方案请注意,在您提取大小为 X 的节点后(现在您可以放松......)它可以达到的最大尺寸是 X+W。所有其他数字都大于 X(因为你从队列中拿走了最小值)所以你在队列中只有 O(W) 个不同的数字,所以你可以将它用作二进制堆,然后每一步都将花费 O(logW) 并且所有在一起将是:(V+E)logW.
关于algorithm - 边权有限的图上的 Dijkstra 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16272104/
我是一名优秀的程序员,十分优秀!