Dijkstra在邊緣權值有限的圖上的算法

假設我們想在邊緣權重爲範圍內的整數的圖上運行Dijkstra算法，其中W是一個相對較小的數。如何在O((|V|+|E|)logW)中找到從頂點s到t的最短路徑？Dijkstra在邊緣權值有限的圖上的算法

我從S. Dasgupta，C. Papadimitriou和U. Vazirani的算法中遇到了這個問題。我可以證明，如果我們像以前一樣實現Dijkstra算法，那麼在每次迭代時，優先級隊列中節點的距離範圍將在W之內。但是，由於優先級隊列沒有將具有相同權重的元素放入同一個桶中的屬性，因此此觀察不會直接導致解決問題。

任何人都可以給我一些提示，如何進一步使有界範圍W爲我工作？

謝謝！

來源

2013-04-29 Will Best

嗯，可能通過計數/基數排序，優先級隊列的排序可能會更快。現在更新（刪除+插入）元素現在可以更快，因爲隊列可以是數組數組（或數組的排序映射） – Karussell 2013-04-30 09:22:40

在講座[Courses.MIT]中給出解決方案（_Bounded Integer Edge Weights_問題）（http://courses.csail.mit.edu/6.006/spring11/rec/rec16.pdf）。此外，它的時間複雜度是線性的$ O（| V | + | E |）$。 – hengxin 2013-11-25 06:58:33

您的優先級隊列中可以有多少個不同的號碼？

解決方案 注意，您提取與大小X的節點後（現在你放鬆..）最大尺寸可以達到爲X + W。所有其他數字都比X大（因爲您從隊列中取最小值）因此您在隊列中只有O（W）個不同的數字，因此您可以將它用作二進制堆，然後每一步都將花費O （logW）並且全部一起將是：（V + E）logW。

來源

2014-01-23 14:30:44 member555

Dijkstra在邊緣權值有限的圖上的算法

回答

相關問題