Master DSA: Dijkstra's Algorithm (Shortest Path from Source)

Dijkstra's algorithm is a cornerstone graph algorithm designed to find the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights. By leveraging a greedy strategy and a binary min-heap (Priority Queue), it systematically explores the graph to guarantee optimal path distances in $O((V + E) \log V)$ time complexity.

1. The Core Problem: Single-Source Shortest Path

In graph theory, finding the shortest path between nodes is a fundamental problem with applications ranging from GPS navigation to network packet routing.

Why Standard BFS Fails on Weighted Graphs

In an unweighted graph, a simple Breadth-First Search (BFS) is sufficient to find the shortest path because the "distance" is measured purely by the number of edges. BFS explores the graph level by level, ensuring that the first time a node is reached, it is reached via the shortest path.

However, when edges have varying weights (representing distance, time, or cost), BFS fails. A path with fewer edges might have a much higher cumulative weight than a path with more edges.

In the weighted graph above, BFS would incorrectly choose the top path to reach node 2 first (1 edge vs 2 edges), ignoring the fact that the bottom path has a significantly lower total weight. Dijkstra's algorithm solves this exact limitation.

2. Fundamental Properties & Constraints

To apply Dijkstra's algorithm correctly, you must understand its core mathematical constraints and algorithmic design:

• Single-Source Focus: It calculates the shortest path from one designated source node to all other nodes in the graph.

• Weighted Edges: Every edge must have a numerical weight representing the cost of traversing that edge.

• Non-Negative Weights Constraint:

  Important: Dijkstra's algorithm only works when all edge weights are non-negative ($weight \ge 0$).

  If the graph contains negative edge weights, the greedy assumption of Dijkstra breaks down. Once a node is marked as "processed" (popped from the priority queue), Dijkstra assumes its shortest path has been finalized. A negative edge weight elsewhere in the graph could later decrease the cost of an already processed node, violating this assumption and leading to incorrect results. For graphs with negative weights, the Bellman-Ford algorithm must be used instead.

• Greedy Strategy: At each step, the algorithm greedily selects the unvisited node with the smallest tentative distance to process next.

3. The Mental Model & Real-World Analogy

Real-Life Analogy: The Water Ripple Effect

Imagine a network of pipes (edges) connecting various reservoirs (nodes). The length of each pipe represents its edge weight.

If you pour water into the source reservoir (Node 0), the water will flow through all connected pipes at a constant speed.

• The water will reach the closest reservoir first.
• As soon as water reaches any reservoir, that path represents the absolute fastest (shortest) way to get there.
• The water continues to ripple outward, finding the optimal path to every single reservoir in the network based on the physical constraints of the pipe lengths.

Dijkstra's algorithm simulates this ripple effect digitally using a Priority Queue (Min-Heap) to track which "reservoir" the water reaches next.

4. Dijkstra's Algorithm Step-by-Step Workflow

The algorithm maintains a state of tentative distances and systematically updates them.

Mathematical Formula (Edge Relaxation)

The core operation of Dijkstra's algorithm is relaxation. For any edge from node $u$ to node $v$ with weight $w$:

This formula checks if traveling to node $v$ through node $u$ is shorter than the currently known shortest path to $v$.

The Step-by-Step Execution Plan

5. Visualizing the Graph & Step-by-Step Trace

Let us trace the algorithm using the exact graph demonstrated by the creator.

The Target Graph

• Nodes: 0, 1, 2, 3, 4
• Bidirectional Edges & Weights:
  • 0 <-> 1 (Weight: 2)
  • 0 <-> 2 (Weight: 4)
  • 1 <-> 2 (Weight: 1)
  • 2 <-> 3 (Weight: 7)
  • 2 <-> 4 (Weight: 3)
  • 3 <-> 4 (Weight: 1)

Trace Table of Distance Array Updates

Initially, all distances are set to $\infty$ except the source node 0, which is set to 0.

Detailed Walkthrough of the Trace

1. Step 1: Process Node 0
   • Pop (0, 0).
   • Neighbors of 0 are 1 (weight 2) and 2 (weight 4).
   • dist[1] becomes $\min(\infty, 0 + 2) = 2$. Push (2, 1).
   • dist[2] becomes $\min(\infty, 0 + 4) = 4$. Push (4, 2).
2. Step 2: Process Node 1
   • Pop (2, 1) (since 2 is smaller than 4 in the Min-Heap).
   • Neighbors of 1 are 0 and 2.
   • For 2: new_dist = dist[1] + weight(1, 2) = 2 + 1 = 3.
   • Since $3 < 4$ (current dist[2]), update dist[2] = 3. Push (3, 2).
3. Step 3: Process Node 2
   • Pop (3, 2).
   • Neighbors of 2 are 0, 1, 3 (weight 7), and 4 (weight 3).
   • For 3: new_dist = 3 + 7 = 10. Update dist[3] = 10. Push (10, 3).
   • For 4: new_dist = 3 + 3 = 6. Update dist[4] = 6. Push (6, 4).
4. Step 4: Handle Stale Entry (4, 2)
   • Pop (4, 2).
   • Since the popped distance (4) is greater than the currently recorded shortest distance to node 2 (dist[2] = 3), this is a stale path. Skip processing.
5. Step 5: Process Node 4
   • Pop (6, 4).
   • Neighbors of 4 are 2 and 3 (weight 1).
   • For 3: new_dist = dist[4] + weight(4, 3) = 6 + 1 = 7.
   • Since $7 < 10$ (current dist[3]), update dist[3] = 7. Push (7, 3).
6. Step 6: Process Node 3
   • Pop (7, 3). Neighbors are already optimized. No updates.
7. Step 7: Handle Stale Entry (10, 3)
   • Pop (10, 3). Since $10 > dist[3]$ (which is 7), skip.
   • The Priority Queue is now empty. The final shortest path distance array is: [0, 2, 3, 7, 6].

6. Naive vs. Optimized Priority Queue Approach

To understand why a Min-Heap is critical, let's compare the naive approach with the optimized Priority Queue approach.

7. Complete Java Implementation

Below is the complete, production-grade Java implementation of Dijkstra's algorithm matching the creator's design.

import java.util.*;

public class DijkstraAlgorithm {

    // Class representing a node and its associated weight/distance
    static class Pair {
        int node;
        int weight;

        public Pair(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    /**
     * Executes Dijkstra's algorithm to find the shortest path from a source node.
     * 
     * @param adj  The adjacency list representation of the graph
     * @param src  The starting source node
     * @param V    The total number of vertices in the graph
     * @return     An array containing the shortest distances from the source to all nodes
     */
    public static int[] dijkstra(List<List<Pair>> adj, int src, int V) {
        // Initialize distance array with infinity
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        // Base case: distance from source to source is 0
        dist[src] = 0;

        // Min-Heap Priority Queue sorted by weight (distance)
        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.weight));
        
        // Push the source node into the priority queue
        pq.add(new Pair(src, 0));

        while (!pq.isEmpty()) {
            Pair current = pq.poll();
            int u = current.node;
            int d = current.weight;

            // Optimization: Skip processing if we found a shorter path to u already
            if (d > dist[u]) {
                continue;
            }

            // Traverse all neighbors of the current node u
            for (Pair neighbor : adj.get(u)) {
                int v = neighbor.node;
                int weightUV = neighbor.weight;

                // Relaxation Step
                if (dist[u] + weightUV < dist[v]) {
                    dist[v] = dist[u] + weightUV;
                    pq.add(new Pair(v, dist[v]));
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Constructing the bidirectional graph from the lecture
        // Edge 0 - 1 (Weight 2)
        adj.get(0).add(new Pair(1, 2));
        adj.get(1).add(new Pair(0, 2));

        // Edge 0 - 2 (Weight 4)
        adj.get(0).add(new Pair(2, 4));
        adj.get(2).add(new Pair(0, 4));

        // Edge 1 - 2 (Weight 1)
        adj.get(1).add(new Pair(2, 1));
        adj.get(2).add(new Pair(1, 1));

        // Edge 2 - 3 (Weight 7)
        adj.get(2).add(new Pair(3, 7));
        adj.get(3).add(new Pair(2, 7));

        // Edge 2 - 4 (Weight 3)
        adj.get(2).add(new Pair(4, 3));
        adj.get(4).add(new Pair(2, 3));

        // Edge 3 - 4 (Weight 1)
        adj.get(3).add(new Pair(4, 1));
        adj.get(4).add(new Pair(3, 1));

        int sourceNode = 0;
        int[] shortestDistances = dijkstra(adj, sourceNode, V);

        System.out.println("Shortest distances from source node " + sourceNode + ":");
        for (int i = 0; i < V; i++) {
            System.out.println("To node " + i + " -> " + shortestDistances[i]);
        }
    }
}

8. Detailed Code Walkthrough & Execution Flow

Let's break down the execution flow of the dijkstra method:

Key Code Blocks Explained

• Min-Heap Comparator:

  JAVA

  Copy

  PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.weight));
  

  This ensures that the pair with the absolute smallest cumulative distance is always at the top of the queue, satisfying the greedy choice property.

• Stale Path Optimization:

  JAVA

  Copy

  if (d > dist[u]) {
      continue;
  }
  

  Because Java's standard PriorityQueue does not support an efficient $O(\log V)$ decreaseKey operation out of the box, we instead push a new Pair with the updated shorter distance whenever we relax an edge. This leaves the old, longer path pair in the queue. This check instantly discards those outdated, stale pairs when they are eventually popped, preventing redundant neighbor evaluations.

9. Complexity Analysis

Time Complexity: $O((V + E) \log V)$

• Initialization: Initializing the distance array takes $O(V)$ time.
• Heap Operations:
  • Each vertex is added to the priority queue at least once. In the worst case, we perform $O(V)$ extractions (pop operations), which take $O(V \log V)$ time.
  • For every edge, we might perform a relaxation step and insert a new pair into the heap. Across the entire execution, this results in at most $O(E)$ push operations, taking $O(E \log V)$ time.
• Total Time Complexity: Combining these gives $O((V + E) \log V)$. For a connected graph where $E \ge V$, this is simplified to $O(E \log V)$.

Space Complexity: $O(V + E)$

• Adjacency List: Stores $V$ vertices and $E$ edges, taking $O(V + E)$ space.
• Distance Array: Stores the shortest distance for each vertex, taking $O(V)$ space.
• Priority Queue: In the worst case, stores multiple path entries for vertices, taking up to $O(E)$ space.
• Total Auxiliary Space: $O(V + E)$.

10. Common Pitfalls & Debugging Mindset

When implementing Dijkstra's algorithm in interviews or production, watch out for these common issues:

• Negative Edge Weights:
  • Symptom: Infinite loops or incorrect shortest path values.
  • Fix: Always verify if the input graph contains negative weights. If it does, switch to the Bellman-Ford algorithm.
• Integer Overflow during Relaxation:
  • Symptom: Distances suddenly become negative numbers.
  • Cause: Adding a positive edge weight to Integer.MAX_VALUE causes integer overflow, wrapping the value around to a negative number.
  • Fix: Only perform the addition if the current distance is not equal to Integer.MAX_VALUE:
    JAVA

    Copy

    if (dist[u] != Integer.MAX_VALUE && dist[u] + weightUV < dist[v]) { ... }
    

• Forgetting Bidirectional Edge Additions:
  • Symptom: Nodes are reported as unreachable ($\infty$ distance).
  • Fix: Ensure that for undirected graphs, you add the edge to both adjacency lists: adj.get(u).add(new Pair(v, w)) and adj.get(v).add(new Pair(u, w)).

Summary and Key Takeaways

• Single-Source Shortest Path: Dijkstra's algorithm calculates the shortest path from a single source node to all other nodes in a weighted graph.
• Strict Non-Negative Constraint: It is mathematically restricted to graphs with non-negative edge weights ($weight \ge 0$).
• Greedy Paradigm: It operates on a greedy strategy, always selecting the closest unvisited node to process next.
• Min-Heap Efficiency: Utilizing a Priority Queue (Min-Heap) optimizes the node selection step, reducing the time complexity from $O(V^2)$ to $O((V + E) \log V)$.
• Edge Relaxation: The core formula $dist[v] = \min(dist[v], dist[u] + weight(u, v))$ is systematically applied to update path costs.
• Stale Path Filtering: Checking if (d > dist[u]) continue is a crucial optimization to ignore outdated path entries in the Priority Queue.
• Space Complexity: The algorithm requires $O(V + E)$ auxiliary space to store the graph structure, distances, and priority queue states.