Dijkstra’s Algorithm with a Priority Queue

Learn to implement Dijkstras Algorithm with a Priority Queue using a min-heap (heapq). We cover the problem statement, clear intuition, step-by-step approach, fully commented code, a hand dry-run, Big-O analysis, and key takeaways.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

For a weighted directed graph with non-negative edge weights, return an array dist where
dist[i] = length of the shortest path from a given source vertex src to vertex i.
If a vertex is unreachable, keep its distance as ∞ (or any sentinel like float('inf')).

Although the original GFG statement shows an adjacency matrix, we’ll solve with a more memory-friendly adjacency list; the core logic is identical.

2. Example

V = 5, src = 0
Edges = [
  (0, 1, 4), (0, 2, 1),
  (2, 1, 2), (1, 3, 1),
  (2, 3, 5), (3, 4, 3)
]

Shortest distances from 0 ➜ [0, 3, 1, 4, 7]

• 0 → 2 (1) → 1 ( + 2) = 3
• 0 → 2 (1) → 1 (2) → 3 ( + 1) = 4
• 0 → 2 → 1 → 3 → 4 totals 7

3. Deep intuition & approach

3.1 Why Dijkstra + min-heap?

• A greedy idea underlies the algorithm:
  Among all unexplored vertices, pick the one with the currently smallest tentative distance; lock that distance forever.
• A priority queue (min-heap) lets us pop that “lightest” vertex in O(log V) time.

3.2 Key concepts

1. Distance array – our best-so-far estimates.
2. Visited / relaxed rule – once we pop a vertex from the heap, its distance is final; no shorter path can appear later because all remaining paths are already heavier.
3. Edge relaxation – for each edge u → v with weight w: pythonCopyEditif dist[u] + w < dist[v]: dist[v] = dist[u] + w push (dist[v], v) into heap This may insert multiple copies of v, but only the one with the smallest distance will matter when popped.

3.3 Algorithm outline

1. Build adjacency list from the edge list / matrix.
2. Initialise dist[src] = 0, everything else ∞.
3. Push (0, src) into a min-heap.
4. Loop while heap not empty:
   • Pop (currDist, u) (the lightest vertex).
   • For every neighbour (v, w) of u, relax the edge.
5. Heap eventually empties, leaving dist filled with final shortest paths.

Because edge weights are non-negative, the greedy choice is safe; negative weights would break Dijkstra.

4. Python code

import heapq

class Solution:
    # Returns shortest distances from src to all other vertices
    def dijkstra(self, V, edges, src):
        # -------- 1. Build adjacency list --------
        adj_list = [[] for _ in range(V)]
        for u, v, d in edges:
            adj_list[u].append([v, d])

        # -------- 2. Distance + heap initialisation --------
        distance = [float("inf") for _ in range(V)]
        distance[src] = 0
        priority_queue = [[0, src]]          # (dist, vertex)

        # -------- 3. Main loop --------
        while priority_queue:
            curr_dist, node = heapq.heappop(priority_queue)

            # Skip stale entries
            if curr_dist != distance[node]:
                continue

            # Explore neighbours
            for adjNode, weight in adj_list[node]:
                dist_trav = curr_dist + weight
                if dist_trav < distance[adjNode]:
                    distance[adjNode] = dist_trav
                    heapq.heappush(priority_queue, [dist_trav, adjNode])

        return distance

5. Step-by-step code explanation

6. Dry run on the sample graph

Distances match expected output [0, 3, 1, 4, 7].

7. Complexity analysis

For sparse graphs this is significantly faster than using an adjacency matrix with O(V²) scanning.

8. Conclusion

• Priority-queue Dijkstra elegantly handles non-negative weighted graphs.
• The min-heap pops the next safest vertex, guaranteeing its distance is final.
• Edge relaxation then spreads improvements to neighbours.
• Remember the stale-entry guard to avoid unnecessary relaxations when a better path has already been recorded.

With these principles and the commented code above, you can confidently apply Dijkstra to real-world shortest-path problems.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.