Shortest Path Algorithms

1. Introduction: The GPS Engine

How does Google Maps find the fastest route from your house to the airport? It doesn't check every possible road on Earth. It uses Shortest Path Graph Algorithms.

We already know that Breadth-First Search (BFS) finds the shortest path in an unweighted graph (where every road takes 1 minute). But the real world has weights. A highway might be 10 miles long but take 10 minutes. A city street might be 2 miles long but take 20 minutes.

To solve weighted graphs, we must upgrade from BFS to elite algorithms: Dijkstra's, Bellman-Ford, or Floyd-Warshall. Choosing the wrong one in an interview is an instant red flag.

2. Core Concept: The Big Three

1. Dijkstra’s Algorithm ($O(E \log V)$):

   • Uses a Priority Queue (Min-Heap) instead of a normal Queue.
   • Pro: Extremely fast. The gold standard for 90% of problems.
   • Con: FAILS if the graph has negative edge weights!

2. Bellman-Ford Algorithm ($O(V \times E)$):

   • A Dynamic Programming approach that relaxes all edges $V-1$ times.
   • Pro: Handles negative edge weights perfectly. Can mathematically detect negative weight cycles.
   • Con: Slower than Dijkstra's.

3. Floyd-Warshall Algorithm ($O(V^3)$):

   • Uses a 3D (optimized to 2D) DP matrix.
   • Pro: Finds the shortest path between EVERY pair of nodes simultaneously (All-Pairs Shortest Path).
   • Con: Horrifically slow for large graphs ($V > 400$).

3. Advanced Code Example: Dijkstra's Algorithm

Problem Statement: (LeetCode 743) Network Delay Time. You are given a network of n nodes, labeled from 1 to n. You are given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal.

The Insight: This asks for the maximum of all the shortest paths from node k. We use Dijkstra's Algorithm. Instead of processing nodes level-by-level (BFS), we process them by their cumulative time from the start node using a Min-Heap.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class DijkstrasAlgorithm {
    static class Edge {
        int to, time;
        Edge(int to, int time) {
            this.to = to;
            this.time = time;
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        // 1. Build Adjacency List (1-indexed)
        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] t : times) {
            adj.get(t[0]).add(new Edge(t[1], t[2]));
        }
        
        // 2. Track the minimum time to reach each node
        int[] minTime = new int[n + 1];
        Arrays.fill(minTime, Integer.MAX_VALUE);
        minTime[k] = 0;
        
        // 3. Min-Heap: [node, cumulative_time]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.offer(new int[]{k, 0});
        
        // 4. Dijkstra's Traversal
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            int timeToU = current[1];
            
            // Optimization: If we already found a faster route to 'u' previously, discard this stale path!
            if (timeToU > minTime[u]) continue;
            
            for (Edge edge : adj.get(u)) {
                int v = edge.to;
                int timeToV = timeToU + edge.time;
                
                // Relaxation Step: If this path is strictly faster than our previous best, update it!
                if (timeToV < minTime[v]) {
                    minTime[v] = timeToV;
                    pq.offer(new int[]{v, timeToV});
                }
            }
        }
        
        // 5. Find the maximum time across all nodes (since they all need to receive it)
        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (minTime[i] == Integer.MAX_VALUE) return -1; // Unreachable node!
            maxTime = Math.max(maxTime, minTime[i]);
        }
        
        return maxTime;
    }
}

4. Advanced Code Example: Bellman-Ford Algorithm

Problem Statement: (LeetCode 787) Cheapest Flights Within K Stops. There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i]. Find the cheapest price from src to dst with at most k stops.

The Insight: Dijkstra's algorithm might pick a super cheap route that takes 100 stops. But we have a hard limit of K stops! Bellman-Ford inherently processes graphs level-by-level (by number of edges used). If we run Bellman-Ford exactly K + 1 times, we mathematically guarantee the shortest path using at most K + 1 edges (which is K intermediate stops)!

import java.util.Arrays;

public class BellmanFord {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // Initialize distances
        int[] prices = new int[n];
        Arrays.fill(prices, Integer.MAX_VALUE);
        prices[src] = 0;
        
        // Run exactly K + 1 times
        for (int i = 0; i <= k; i++) {
            // We MUST use a temporary array for this iteration.
            // Otherwise, a single flight update could trigger a chain reaction 
            // of updates, processing multiple stops in a single iteration!
            int[] tempPrices = Arrays.copyOf(prices, n);
            
            for (int[] flight : flights) {
                int u = flight[0];
                int v = flight[1];
                int price = flight[2];
                
                // If the source node is reachable, try to relax the edge
                if (prices[u] != Integer.MAX_VALUE) {
                    if (prices[u] + price < tempPrices[v]) {
                        tempPrices[v] = prices[u] + price;
                    }
                }
            }
            
            prices = tempPrices;
        }
        
        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}

5. Advanced Code Example: Floyd-Warshall Algorithm

Floyd-Warshall is shockingly simple to write. It relies on a 3-nested for loop. The core DP logic: dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]). "Is the distance from $i$ to $j$ faster if we route it through an intermediate node $k$?"

public class FloydWarshall {
    public void allPairsShortestPath(int[][] graph, int V) {
        // Assume graph[i][j] is the weight, and Integer.MAX_VALUE / 2 if no edge exists.
        int[][] dist = new int[V][V];
        
        // 1. Initialize distance matrix
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        
        // 2. The Algorithm
        // k is the intermediate node. It MUST be the outer loop!
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // Can we improve the path from i to j by routing through k?
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
}

6. Common Mistakes Beginners Make

1. Using Dijkstra's on Graphs with Negative Edges

   • The Mistake: Running standard Dijkstra's when edge weights can be $< 0$.
   • Why it's wrong: Dijkstra's uses a Greedy assumption. Once a node is popped from the Min-Heap, it assumes the absolute shortest path to that node has been found and locked in forever. If there's a negative edge later in the graph, it could create a cheaper backdoor to that node! Dijkstra's will completely ignore the backdoor because the node was already marked visited.
   • The Fix: If negative edges exist, you MUST use Bellman-Ford.

2. The "Stale State" Bug in Dijkstra's

   • The Mistake: Pushing updated distances into the Priority Queue, but forgetting to check if (timeToU > minTime[u]) continue; upon popping.
   • Why it's wrong: You might push Node 5 into the heap with a cost of 100. Later, you find a shortcut to Node 5 with a cost of 10. You push [5, 10] into the heap. The heap will pop [5, 10] first and process it correctly. BUT, later on, it will still pop the stale [5, 100] state! If you don't instantly skip it, you will waste massive amounts of time exploring paths from an outdated state, causing Time Limit Exceeded.

3. Wrong Loop Order in Floyd-Warshall

   • The Mistake: Putting the i (source) or j (destination) loop on the outside.
   • Why it's wrong: The algorithm uses DP to build paths allowing nodes $0$ to $k$ as intermediate routing points. If $k$ is not the outermost loop, you might use an intermediate node $k=5$ before you've fully resolved the optimal paths utilizing $k=2$, breaking the mathematical induction of the DP.

7. Interview Q&A

Q1: What is the A (A-Star) Algorithm?* Answer: A* is a highly optimized version of Dijkstra's used heavily in Pathfinding (like Game AI). Instead of searching equally in all directions (like Dijkstra's), it uses a "Heuristic" (like the direct straight-line distance to the target) to bias the Priority Queue towards the physical direction of the goal, drastically reducing the search space.

Q2: How do you detect a Negative Weight Cycle? Answer: A negative cycle is a loop where the sum of edges is negative. If you loop in it forever, your distance becomes negative infinity! To detect it, run Bellman-Ford's main loop $V - 1$ times. Then, run the exact same loop one more time. If any distance updates on the $V^{th}$ pass, it mathematically proves a negative cycle exists, because the longest possible valid path in a graph of $V$ nodes has $V - 1$ edges!

8. Practice Problems

1. Network Delay Time (LeetCode 743)
   • Goal: Master the standard Dijkstra's implementation.
2. Cheapest Flights Within K Stops (LeetCode 787)
   • Goal: Master Bellman-Ford (or a heavily modified Dijkstra's).
3. Path with Maximum Probability (LeetCode 1514)
   • Hint: Dijkstra's doesn't just do addition. If you want maximum probability, use a Max-Heap and MULTIPLY the edge weights!

9. Summary

• Dijkstra's: Min-Heap. $O(E \log V)$. Fails on negative edges. The absolute king of Pathfinding.
• Bellman-Ford: Nested loops relaxing all edges $V-1$ times. $O(V \times E)$. Handles negative edges and limits on stops ($K$).
• Floyd-Warshall: 3D Matrix DP. $O(V^3)$. Finds the shortest path between every single pair of nodes simultaneously.