关于利用堆优化的dijkstra算法的时间复杂度问题

litianhua

作者在《啊哈算法》中写到，dijkstra算法原始算法的时间复杂度是O（n^2），使用邻接表且堆优化寻找离顶点最近距离后，可以使时间复杂度降低到O（(m+n)logn），不知道是怎么得到的？网上找到了一些代码，看了一下，但是水平不够，看不懂。
网上大致的解释是堆优化之后，寻找离顶点距离最近的点这一过程的时间复杂度变为logn，n，m分别是这个图中的点和边的数量，我想问的是最后的结论（m+n）logn这个结论到底是怎么得到的，求一个详细点的说明过程，请诸位大神出手解惑

创世菌

呵呵，我还没有研究透《啊哈！算法》……
Ha ha,I haven't studied "Aha!Algorithms"...

litianhua

创世菌 发表于 2018-3-11 15:08
呵呵，我还没有研究透《啊哈！算法》……
Ha ha,I haven't studied "Aha!Algorithms"...

实际上，logn这部分我能理解，关键是m+n这个理解不了，尤其是关于边数m这块，想不同怎么表述这个

litianhua

创世菌 发表于 2018-3-11 15:08
呵呵，我还没有研究透《啊哈！算法》……
Ha ha,I haven't studied "Aha!Algorithms"...

这样啊，大神也不知道吗？

4399APPLE

考虑最坏情况，每条边均成功松弛，O(MlogN)
考虑堆初始化，O(NlogN)
相加得 O((M+N)logN)

litianhua

4399APPLE 发表于 2018-3-12 18:20
考虑最坏情况，每条边均成功松弛，O(MlogN)
考虑堆初始化，O(NlogN)
相加得 O((M+N)logN)

谢谢指点，已经明白了