假设 G(V,E) 是一个具有正边权值的无向图。Dijkstra单源最短路径算法可以使用二叉堆数据结构实现,时间复杂度为:
1. O(|V|^2)
2. O(|E|+|V|log|V|)
3. O(|V|log|V|)
4. O((|E|+|V|)log|V|)
正确答案是 -
- O((|E|+|V|)log|V|)
我的方法如下 -
O(V+V+VlogV+ElogV) = O(ElogV)
O(V)
初始化。O(V)
建堆。VlogV
执行 Extract_Min。ElogV
执行 Decrease Key。
现在,我得到了 O(ElogV) 的答案,但当我看到选项时,其中一部分告诉我正确答案是 O(VlogV),因为对于稀疏图而言 |V| = |E|,但正如我所说的,正确答案应该是 O((|E|+|V|)log|V|)。那么,我错在哪里了呢?
O(V + E logV)
。我已经问过,但没有得到令人满意的回复:https://math.stackexchange.com/questions/3683910/time-complexity-of-dijkstras-algorithm - martinkunev