混淆下面的Dijkstra算法實現的時間複雜度

我試圖在java中使用Adjacency列表實現Dijkstra。我在java中遇到了Dijkstra的一個實現，但我很困惑它是O（ElogV）解決方案還是0（V^2）解決方案。鏈接到代碼是：http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html。我很困惑，因爲C++中Dijkstra的優化實現涉及優先級隊列的使用，但這裏不使用優先級隊列。混淆下面的Dijkstra算法實現的時間複雜度

2014-09-28 vaibhav.g

也許這更適合：http://cs.stackexchange.com？ – EWit 2014-09-28 10:06:59

事實上，使用優先級隊列很方便，在鏈接的實現中，通過線性探索_ALL THE VERTICES_而不是僅取最小優先級隊列的頂部來獲取最小距離頂點！這顯然不是最理想的，儘管它與使用優先級隊列相同。 – Rerito 2014-09-28 20:36:03

所以你想說，雖然給定代碼的時間複雜度是O（ElogV），但代碼可以更高效 – 2014-09-30 07:13:49

-1

使用鄰接表的Dijkstra算法的時間複雜度爲

隨着鄰接表和優先級隊列：

O((v+e) log v)。如果圖形密集，則e將是v^2。（佛例如，一個完整的圖有(n(n/1)/2) = O(v^2)邊緣，所以e >> v）

對於更密集的曲線圖中，我們可以使用一個斐波納契堆代替一個優先級隊列的。

隨着鄰接表和Fibonacci堆：

TC將O(e + v log v)
因爲更緻密的圖表e ~ v^2
TC將O(v^2 + v log v) ~ O(v^2)

2017-06-07 14:21:06

回答