Dijkstra's with Array-Based Priority Queue
What you'll learn: How to implement Dijkstra's algorithm using a simple array to track and extract the minimum distance vertex, resulting in O(V²) time complexity.
The Core Idea
Instead of using a fancy priority queue, you can implement Dijkstra's algorithm with just a plain array that stores distances. At each step, you scan the entire array to find the unvisited vertex with the smallest distance value. This is simple to code but takes O(V) time per extraction, leading to O(V²) overall time.
How It Works
You maintain:
- A
dist[]array holding the shortest known distance to each vertex - A
visited[]boolean array marking which vertices are finalized
Each iteration:
- Linear scan through all vertices to find the unvisited one with minimum
distvalue (O(V)) - Mark that vertex as visited
- Relax all its outgoing edges (update neighbors' distances if you found a shorter path)
Since you perform V extractions (one per vertex), and each extraction scans V vertices, the total is O(V²).
When to Use This Approach
This array-based implementation is actually efficient for dense graphs where E ≈ V². Since relaxing all edges takes O(E) time anyway, the O(V²) extraction cost doesn't dominate. It's also simpler to implement than a heap-based priority queue.
For sparse graphs (where E << V²), using a binary heap or Fibonacci heap is faster.
Key Takeaway: Dijkstra's with array-based priority queue achieves O(V²) time by linearly scanning for the minimum distance vertex at each step—simple and effective for dense graphs.