经典算法研究系列:二之再续 Dijkstra 算法+fibonacci堆的逐步c实现(二)

2014-11-23 21:45:58 · 作者: · 浏览: 33
看最小优先队列的三种实现方法比较:

EXTRACT-MIN + RELAX
I、 简单方式: O(V*V + E*1)
II、 二叉/项堆: O(V*lgV + |E|*lgV)
源点可达:O(E*lgV)
稀疏图时,有E=o(V^2/lgV),