Dijkstra's Shortest Path

Introduction

In our post on Breadth-First Search (BFS), we learned that BFS is perfect for finding the shortest path between point A and point B.

But there is a massive catch: BFS only works on unweighted graphs. It assumes that taking an edge from A $\rightarrow$ B costs exactly 1 unit of effort, just like A $\rightarrow$ C.

What if A $\rightarrow$ C is a direct highway taking 10 minutes, but A $\rightarrow$ B $\rightarrow$ C is a scenic mountain pass taking 60 minutes? BFS would wrongly claim that A $\rightarrow$ C is the “shortest” route just because it has fewer stops.

To find the true shortest path based on weights (time, distance, cost), we need an algorithm invented by computer science pioneer Edsger W. Dijkstra in 1956.

The Concept Behind Dijkstra

Dijkstra’s Algorithm is essentially a smarter version of BFS.

Standard BFS uses a standard Queue (FIFO). It processes nodes strictly in the order they were discovered.

Dijkstra uses a Priority Queue (Min-Heap). Instead of exploring nodes in the order they were discovered, it always explores the node that is currently cheapest to reach from the start.

The Rules of the Game

1. We keep a ledger of the absolute shortestPath known from the Start node to every other node. Initially, these are all Infinity.
2. The distance to the Start node itself is 0.
3. We put the Start node in a Min-Heap.
4. We pop the cheapest node from the heap.
5. We look at its neighbours. If we can reach a neighbour cheaper through the current node than any previously known path, we update the ledger and push that neighbour into the heap.

Step-by-Step Walkthrough

Let’s find the shortest path from Start (A) to Target (E).

Initial Ledger: A=0, B=∞, C=∞, D=∞, E=∞ Heap: [(A, 0)]

Step 1: Pop A (cost 0).

• Neighbour B: Cost A $\rightarrow$ B is $0 + 4 = 4$. $4 < ∞$. Update ledger. Push (B, 4).
• Neighbour C: Cost A $\rightarrow$ C is $0 + 2 = 2$. $2 < ∞$. Update ledger. Push (C, 2). Ledger: A=0, B=4, C=2, D=∞, E=∞. Heap: [(C, 2), (B, 4)]

Step 2: Pop C (cost 2). (Notice how the Priority Queue chose C before B!)

• Neighbour B: Cost A $\rightarrow$ C $\rightarrow$ B is $2 + 1 = 3$. $3 < 4$. Update ledger! Push (B, 3).
• Neighbour D: Cost A $\rightarrow$ C $\rightarrow$ D is $2 + 8 = 10$. $10 < ∞$. Update. Push (D, 10).
• Neighbour E: Cost A $\rightarrow$ C $\rightarrow$ E is $2 + 10 = 12$. $12 < ∞$. Update. Push (E, 12). Ledger: A=0, B=3, C=2, D=10, E=12. Heap: [(B, 3), (B, 4), (D, 10), (E, 12)]

Step 3: Pop B (cost 3).

• Neighbour D: Cost A $\rightarrow$ C $\rightarrow$ B $\rightarrow$ D is $3 + 5 = 8$. $8 < 10$. Update ledger! Push (D, 8). Ledger: A=0, B=3, C=2, D=8, E=12. Heap: [(B, 4), (D, 8), (D, 10), (E, 12)]

Step 4: Pop B (cost 4).

• Wait! The ledger says the best path to B is 3. We are looking at a stale node with cost 4. Skip it.

Step 5: Pop D (cost 8).

• Neighbour E: Cost A $\rightarrow$ C $\rightarrow$ B $\rightarrow$ D $\rightarrow$ E is $8 + 2 = 10$. $10 < 12$. Update! Push (E, 10). Ledger: A=0, B=3, C=2, D=8, E=10. Heap: [(E, 10), (D, 10), (E, 12)]

Step 6: Pop E (cost 10).

• This is our target! The absolute cheapest way to reach E costs 10.
• Path: A -> C -> B -> D -> E

Java Implementation

To implement Dijkstra, we need a small helper class to store the node and its current cost together in the Priority Queue.

import java.util.*;

public class Dijkstra {
    
    // Helper class for Priority Queue
    static class PathNode implements Comparable<PathNode> {
        String name;
        int currentCost;

        public PathNode(String name, int currentCost) {
            this.name = name;
            this.currentCost = currentCost;
        }

        // Min-Heap based on cost
        @Override
        public int compareTo(PathNode other) {
            return Integer.compare(this.currentCost, other.currentCost);
        }
    }

    // Graph where String maps to a List of Edge objects (targetNode, weight)
    public static int findShortestPath(Map<String, Map<String, Integer>> graph, 
                                       String start, String target) {
        
        PriorityQueue<PathNode> pq = new PriorityQueue<>();
        Map<String, Integer> shortestCosts = new HashMap<>();

        // Start node costs 0
        pq.offer(new PathNode(start, 0));
        shortestCosts.put(start, 0);

        while (!pq.isEmpty()) {
            PathNode current = pq.poll();

            // Did we hit the target?
            if (current.name.equals(target)) {
                return current.currentCost;
            }

            // OPTIMISATION: If we found a shorter path to this node already, ignore this stale PathNode
            if (current.currentCost > shortestCosts.getOrDefault(current.name, Integer.MAX_VALUE)) {
                continue;
            }

            // Check all neighbours
            Map<String, Integer> neighbours = graph.getOrDefault(current.name, new HashMap<>());
            for (Map.Entry<String, Integer> edge : neighbours.entrySet()) {
                String neighbour = edge.getKey();
                int weight = edge.getValue();
                
                int newCost = current.currentCost + weight;

                // Relaxation: If the new cost is cheaper, update and push to queue
                if (newCost < shortestCosts.getOrDefault(neighbour, Integer.MAX_VALUE)) {
                    shortestCosts.put(neighbour, newCost);
                    pq.offer(new PathNode(neighbour, newCost));
                }
            }
        }

        return -1; // Target unreachable
    }
}

Complexity

The Fatal Flaw: Negative Weights

Dijkstra makes one critical assumption: all edge weights must be positive.

Why? Because Dijkstra assumes that once you pop a node from the Min-Heap, you have found the absolute cheapest way there. If a path later in the graph had a “negative cost” (like a time-travel wormhole), it would ruin Dijkstra’s greedy assumptions. (If you have negative weights, you must use the slower Bellman-Ford Algorithm).

Practice Problems

1. Network Delay Time – LeetCode #743 — The purest Dijkstra problem. Find the time it takes for a signal to reach all nodes.
2. Cheapest Flights Within K Stops – LeetCode #787 — A brilliant variation where you must track both cost AND number of stops.
3. Path with Maximum Probability – LeetCode #1514 — Instead of finding the minimum sum of costs, find the maximum product of probabilities. Just swap to a Max-Heap!

What’s Next?

Phase 3 (Trees & Graphs) is complete! You now understand the structures that hold the world’s most complex data.

In Phase 4, we move away from specific data structures and focus on advanced puzzle-solving techniques, beginning with Dynamic Programming & Memoization.