Search code examples
algorithmlanguage-agnostictime-complexity

Complexity of Dijkstra shortest path

I don't seem to understand Wikipedia's paragraph on why Dijkstra shortest path problem is O((|E|+|V|)*log(|V|))

Supposing that I used a binary heap, extracting all vertices would require V*logV, where does the E*logV term come from?

Can somebody enlighten me please?

Solution

  • When you extract a vertex from the heap, you then need to examine all the edges coming out of that node and do some processing for each neighbour (decreasing key).

    This means that we end up examining all edges during the entire algorithm, and may require O(logV) for each edge, so total of O(ElogV) in addition to the O(VlogV) cost for removing the minimum entry from the heap for each vertex.