Course contentsShow
← Computer Science
Lesson 613 of 2,87214. Heaps and Priority QueuesFree lesson

Dijkstra's Algorithm with Priority Queue

Apply priority queues to efficiently select the minimum-distance vertex in Dijkstra's shortest path algorithm.

Dijkstra's Algorithm with Priority Queue

What You'll Learn

You'll discover how priority queues transform Dijkstra's shortest path algorithm from a slow, tedious process into an efficient graph search powerhouse.

The Core Problem

Dijkstra's algorithm finds the shortest path from a starting vertex to all other vertices in a weighted graph. The basic version repeatedly scans all vertices to find the one with the smallest tentative distance—painfully slow for large graphs.

Priority Queue to the Rescue

Instead of scanning every vertex, use a min-heap priority queue to instantly retrieve the vertex with minimum distance!

Here's how it works:

  1. Initialize: Insert the start vertex with distance 0 into the priority queue
  2. Extract minimum: Use extract-min to get the unvisited vertex with smallest known distance
  3. Update neighbors: For each neighbor, calculate new potential distances; if improved, update the distance and insert/decrease-key in the priority queue
  4. Repeat: Continue until the queue is empty or you've reached your target

The Performance Boost

Without priority queue: Each iteration scans O(V) vertices → O(V²) total time

With min-heap priority queue: Extract-min is O(log V), and you perform O(E) edge relaxations → O((V + E) log V) total time

For sparse graphs where E is much smaller than V², this is dramatically faster!

Real-World Analogy

Imagine finding the cheapest flight path. Without a priority queue, you'd check every airport's price list repeatedly. With a priority queue, you always grab the cheapest known option first—like a smart traveler who sorts deals automatically.

Key Takeaway: Using a min-heap priority queue in Dijkstra's algorithm reduces the vertex-selection bottleneck from O(V) per iteration to O(log V), making pathfinding practical for large graphs.