迪杰斯特拉线性

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)的问题。这很直截了当，虽然乏味。