Question

Let G (V, E) an undirected graph with positive edge weights. Dijkstra's single source-shortest path algorithm can be implemented using the binary heap data structure with time complexity?

• A. $O\left(\right(|E|+|V|\left)\text{log}|V|\right)$
• B. $O\left(|V{|}^2\right)$
• C. $O\left(|V|\text{log}|V|\right)$
• D. $O(|E|+|V|\text{log}|V|)$

Answer 1

The correct option is D $O(|E|+|V|\text{log}|V|)$

Dijkstra's implementation for single source shortest path

(i) Using binary heap takes

$O\left(\right(|E|+|V|\left)\text{log}|V|\right)$

(ii) Using Fibonacci heap takes

$O(|E|+|V|\text{log}|V|)$