Shortest Path

🗺️ Finding the Shortest Path: A GPS Adventure!

Imagine you’re a delivery driver with a super-smart GPS. Your job? Find the fastest route to deliver packages across town. But here’s the twist—some roads are short, some are long, and some even have tolls (negative costs) that PAY you to drive on them!

This is exactly what Shortest Path Algorithms do. They’re the brains behind every navigation app, network router, and game AI that needs to find the best route from Point A to Point B.

🎯 What We’ll Explore

Think of a city map as a graph:

• Nodes = Intersections (places you can visit)
• Edges = Roads connecting them
• Weights = Distance or time to travel each road

Our mission: Find the shortest total distance from a starting point to other destinations!

🚗 Dijkstra’s Algorithm

The Story

Meet Dijkstra (sounds like “DIKE-stra”), our careful GPS navigator. He’s a bit paranoid—he ONLY trusts roads with positive distances. No shortcuts that magically give you negative time!

How It Works (Like a Growing Circle)

Imagine dropping a stone in water. The ripples spread outward, reaching closer points first. That’s Dijkstra!

1. Start at your origin. Distance = 0.
2. Look around at all neighbors.
3. Pick the closest unvisited node.
4. Update distances to its neighbors.
5. Repeat until you’ve visited everyone!

graph TD
    A["Start: Distance 0"] --> B["Check Neighbors"]
    B --> C["Pick Closest Unvisited"]
    C --> D["Update Neighbor Distances"]
    D --> E{All Visited?}
    E -->|No| B
    E -->|Yes| F["Done! 🎉"]

Simple Example

Imagine 3 houses: A, B, C

A --5--> B --2--> C
A --------7-------> C

From A to C:

• Direct path: A → C = 7
• Via B: A → B → C = 5 + 2 = 7

Both are equal! Dijkstra finds this by:

1. Start at A (distance 0)
2. Visit B (distance 5)
3. From B, reach C (distance 7)
4. Compare with direct A→C (also 7)

Java Code

// Dijkstra's Algorithm
import java.util.*;

public class Dijkstra {
    public int[] shortestPath(
        int n,
        List<int[]>[] graph,
        int start
    ) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // Min-heap: [distance, node]
        PriorityQueue<int[]> pq =
            new PriorityQueue<>(
                (a, b) -> a[0] - b[0]
            );
        pq.offer(new int[]{0, start});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];

            if (d > dist[u]) continue;

            for (int[] edge : graph[u]) {
                int v = edge[0];
                int w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(
                        new int[]{dist[v], v}
                    );
                }
            }
        }
        return dist;
    }
}

Time Complexity: O((V + E) log V) with a priority queue

Key Rule: ⚠️ Only works with non-negative edge weights!

⚡ Bellman-Ford Algorithm

The Story

What if some roads GIVE you money to drive on them? (Negative weights!) Dijkstra gets confused, but Bellman-Ford doesn’t!

Think of it like this: Bellman-Ford is a patient teacher who checks every student’s homework V-1 times (where V = number of students). By the end, everyone has the correct answer!

Why V-1 Times?

In a graph with V nodes, the longest possible shortest path has at most V-1 edges. So we need V-1 rounds to guarantee we’ve found everything!

How It Works

1. Set all distances to ∞, except start = 0
2. Repeat V-1 times:
   • For EVERY edge, try to improve distances
3. Check one more time for negative cycles

graph TD
    A["Set All Distances to ∞"] --> B["Start Node = 0"]
    B --> C["Repeat V-1 Times"]
    C --> D["Check Every Edge"]
    D --> E["Update If Shorter"]
    E --> F{Done V-1 Rounds?}
    F -->|No| C
    F -->|Yes| G["Check for Negative Cycles"]
    G --> H["Return Results 🎉"]

Example with Negative Edge

A --4--> B ---(-2)---> C
A --------3---------> C

From A:

• Direct to C: 3
• Via B: 4 + (-2) = 2 ✅ Better!

Bellman-Ford catches this!

Java Code

// Bellman-Ford Algorithm
public class BellmanFord {
    public int[] shortestPath(
        int n,
        int[][] edges,
        int start
    ) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // Relax all edges V-1 times
        for (int i = 0; i < n - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0];
                int v = edge[1];
                int w = edge[2];
                if (dist[u] != Integer.MAX_VALUE
                    && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        // Check for negative cycles
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            int w = edge[2];
            if (dist[u] != Integer.MAX_VALUE
                && dist[u] + w < dist[v]) {
                // Negative cycle detected!
                return null;
            }
        }
        return dist;
    }
}

Time Complexity: O(V × E) — slower but handles negative weights!

🚶 Shortest Path in Unweighted Graph

The Story

What if all roads are exactly the same length? Like walking on a chessboard where each step costs 1?

Here, we don’t need fancy algorithms. Simple BFS (Breadth-First Search) does the trick!

Why BFS Works

BFS explores nodes level by level. First, all nodes 1 step away. Then 2 steps. Then 3. The first time you reach a node, that’s the shortest path!

graph TD
    A["Start"] --> B1["Level 1"]
    A --> B2["Level 1"]
    B1 --> C1["Level 2"]
    B1 --> C2["Level 2"]
    B2 --> C3["Level 2"]

Java Code

// BFS for Unweighted Graph
public int[] bfsShortestPath(
    int n,
    List<Integer>[] graph,
    int start
) {
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    dist[start] = 0;

    Queue<Integer> queue =
        new LinkedList<>();
    queue.offer(start);

    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : graph[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
    return dist;
}

Time Complexity: O(V + E) — super fast!

📡 Network Delay Time

The Problem

You’re a network admin sending a signal from one server. How long until ALL servers receive it?

This is classic Dijkstra! Find the shortest path to every node, then return the maximum of those times.

Example

Server 1 --2--> Server 2 --3--> Server 3
Server 1 --------4-------> Server 3

From Server 1:

• To Server 2: 2
• To Server 3: min(4, 2+3) = 4

Answer: 4 (time for the slowest server)

Java Code (LeetCode 743)

public int networkDelayTime(
    int[][] times,
    int n,
    int k
) {
    // Build graph
    List<int[]>[] graph = new List[n + 1];
    for (int i = 0; i <= n; i++) {
        graph[i] = new ArrayList<>();
    }
    for (int[] t : times) {
        graph[t[0]].add(
            new int[]{t[1], t[2]}
        );
    }

    // Dijkstra
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;

    PriorityQueue<int[]> pq =
        new PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );
    pq.offer(new int[]{0, k});

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        if (d > dist[u]) continue;

        for (int[] edge : graph[u]) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(
                    new int[]{dist[v], v}
                );
            }
        }
    }

    // Find max delay
    int maxDelay = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) {
            return -1; // Unreachable
        }
        maxDelay = Math.max(maxDelay, dist[i]);
    }
    return maxDelay;
}

✈️ Cheapest Flights Within K Stops

The Problem

You’re booking a flight from City A to City B. You can have at most K layovers. What’s the cheapest price?

This is Bellman-Ford with a twist! We only relax edges K+1 times (K stops = K+1 flights).

Why Modified Bellman-Ford?

Regular Dijkstra is greedy—it might take a longer path with more stops just because it’s cheaper. But we have a stop limit!

Example

A --100--> B --100--> C
A --------500-------> C

With K=0 stops: A → C = 500 (direct only) With K=1 stop: A → B → C = 200 ✅

Java Code (LeetCode 787)

public int findCheapestPrice(
    int n,
    int[][] flights,
    int src,
    int dst,
    int k
) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // K stops = K+1 edges
    for (int i = 0; i <= k; i++) {
        // Copy to avoid using
        // same-round updates
        int[] temp = dist.clone();

        for (int[] f : flights) {
            int u = f[0];
            int v = f[1];
            int w = f[2];
            if (dist[u] != Integer.MAX_VALUE
                && dist[u] + w < temp[v]) {
                temp[v] = dist[u] + w;
            }
        }
        dist = temp;
    }

    return dist[dst] == Integer.MAX_VALUE
        ? -1
        : dist[dst];
}

Key Insight: We copy the array each round to avoid using updates from the same round (which would mean more stops)!

🔲 Shortest Path in Binary Matrix

The Problem

You have a grid of 0s and 1s. Start at top-left, reach bottom-right. You can move in 8 directions (including diagonals). Find the shortest path through only 0s.

This is BFS on a grid! Each cell is a node, and you can move to 8 neighbors.

Example

0 0 0
1 1 0
1 1 0

Path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) Length: 5 cells

Java Code (LeetCode 1091)

public int shortestPathBinaryMatrix(
    int[][] grid
) {
    int n = grid.length;
    if (grid[0][0] == 1 ||
        grid[n-1][n-1] == 1) {
        return -1;
    }

    int[][] dirs = {
        {0,1}, {1,0}, {0,-1}, {-1,0},
        {1,1}, {1,-1}, {-1,1}, {-1,-1}
    };

    Queue<int[]> queue =
        new LinkedList<>();
    queue.offer(new int[]{0, 0, 1});
    grid[0][0] = 1; // Mark visited

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int r = curr[0];
        int c = curr[1];
        int dist = curr[2];

        if (r == n-1 && c == n-1) {
            return dist;
        }

        for (int[] d : dirs) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr >= 0 && nr < n &&
                nc >= 0 && nc < n &&
                grid[nr][nc] == 0) {
                grid[nr][nc] = 1;
                queue.offer(
                    new int[]{nr, nc, dist+1}
                );
            }
        }
    }
    return -1;
}

Why BFS? All moves cost 1 (unweighted), so BFS finds the shortest path!

🎯 Quick Comparison

🏆 Key Takeaways

1. Dijkstra = Greedy, fast, no negative weights
2. Bellman-Ford = Patient, handles negatives, detects cycles
3. BFS = Perfect for unweighted/grid problems
4. Network Delay = Dijkstra + find maximum
5. K Stops = Modified Bellman-Ford with limited rounds
6. Binary Matrix = BFS with 8 directions

You’re now ready to navigate any graph like a GPS pro! 🗺️✨