迪傑斯特拉線性

Question

首先：Dijkstras最短路徑算法的一般運行時間是

其中m是邊緣的和數目n個頂點

的數量

二：預計decreasekey操作數是以下

三：與二進制堆Dijkstra算法的預期運行時間，允許在日誌中的所有操作（n）的時間是

但是，爲什麼在稠密的圖的運行時間，如果線性我們考慮一個密度圖如果

有人可以幫助在這裏的O符號和日誌計算？

Answer 1

我的解決方案現在以下

Answer 2

首先，它是不難表明，如果m是n log(n) log(log(n))大歐米伽然後log(n)是log(m)大歐米伽。因此，您可以顯示m是n log(m) log(log(m))的大歐米茄。

由此您可以證明n是m/(log(m) log(log(m)))的大歐米茄。

替代這回你在第三點有表達，我們得到了預期的運行時間爲：

O(m + n log(m/n) log(n)) 

        m             m 
    = O(m + (------------------) log(log(m) log(log(m))) log(------------------) 
      log(m) log(log(m))        log(m) log(log(m)) 

從這裏你可以展開所有的產品日誌到日誌的總和。你會得到很多條款。然後這只是一個證明每個人都是O(m)或o(m)的問題。這很直截了當，雖然乏味。