Shortest Path

🗺️ Graph Algorithms: Shortest Path

The Magical Map Adventure

Imagine you’re a delivery person in a big city. You have packages to deliver to different houses. But here’s the thing — you want to find the quickest way to each house. Not the longest. Not the scenic route. The SHORTEST PATH.

That’s exactly what shortest path algorithms do! They’re like GPS navigation for computers.

🎯 What is a Shortest Path?

Think of a city as a web of roads connecting different places.

     [A]---5---[B]
      |         |
      2         3
      |         |
     [C]---1---[D]

Question: What’s the shortest path from A to D?

• A → B → D = 5 + 3 = 8
• A → C → D = 2 + 1 = 3 ✅

The shortest path is A → C → D with total cost 3!

🧙‍♂️ Dijkstra’s Algorithm

The Greedy Explorer

Story Time: Imagine a curious explorer named Dijkstra. He wants to visit every city starting from his home. But he’s smart — he always visits the closest unvisited city first!

How Dijkstra Thinks

1. Start at home. Distance to home = 0
2. Look around. Which neighbor is closest?
3. Visit it. Mark it as “done”
4. Update distances. Can we reach other cities faster through here?
5. Repeat until everyone is visited!

Visual Example

graph TD
    A["🏠 Start: 0"] -->|4| B["City B"]
    A -->|2| C["City C"]
    B -->|3| D["City D"]
    C -->|1| D
    C -->|5| B

Step by step:

JavaScript Code

function dijkstra(graph, start) {
  const dist = {};
  const visited = new Set();
  const pq = [[0, start]];

  // Set all distances to infinity
  for (let node in graph) {
    dist[node] = Infinity;
  }
  dist[start] = 0;

  while (pq.length > 0) {
    // Sort and get smallest
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();

    if (visited.has(u)) continue;
    visited.add(u);

    for (let [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

⚠️ Important Rule

Dijkstra ONLY works when all edge weights are positive (no negative numbers)!

🔔 Bellman-Ford Algorithm

The Patient Detective

Story Time: Meet Detective Bellman-Ford. Unlike the greedy explorer, this detective is patient. He checks every single road in the city, not once, but many times. Why? To catch negative weight edges!

The Magic of Patience

Bellman-Ford relaxes (updates) every edge V-1 times, where V is the number of vertices.

Why V-1? Because the longest shortest path can have at most V-1 edges!

How It Works

For (V-1) rounds:
  For each edge (u, v) with weight w:
    If dist[u] + w < dist[v]:
      dist[v] = dist[u] + w

Visual Example

graph LR
    A["A: 0"] -->|4| B["B"]
    A -->|5| C["C"]
    B -->|-3| C

Round 1:

• A→B: dist[B] = 0 + 4 = 4
• A→C: dist[C] = 0 + 5 = 5
• B→C: dist[C] = 4 + (-3) = 1 ✅

The negative edge helped us find a shorter path!

JavaScript Code

function bellmanFord(n, edges, start) {
  const dist = Array(n).fill(Infinity);
  dist[start] = 0;

  // Relax V-1 times
  for (let i = 0; i < n - 1; i++) {
    for (let [u, v, w] of edges) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // Check for negative cycle
  for (let [u, v, w] of edges) {
    if (dist[u] + w < dist[v]) {
      return "Negative cycle!";
    }
  }
  return dist;
}

✨ Superpower

Bellman-Ford can detect negative cycles — loops that keep making paths shorter forever!

🚶 Shortest Path in Unweighted Graph

The Simple Walker

Story Time: Imagine all roads are exactly the same length. No tolls. No shortcuts. Just equal steps everywhere.

In this simple world, finding the shortest path is easy — just use BFS (Breadth-First Search)!

Why BFS Works

BFS explores level by level:

• First, all places 1 step away
• Then, all places 2 steps away
• And so on…

graph TD
    A["Start"] --> B["1 step"]
    A --> C["1 step"]
    B --> D["2 steps"]
    C --> E["2 steps"]
    D --> F["3 steps"]

JavaScript Code

function shortestPath(graph, start, end) {
  const queue = [[start, 0]];
  const visited = new Set([start]);

  while (queue.length > 0) {
    const [node, dist] = queue.shift();

    if (node === end) return dist;

    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1; // No path found
}

🎯 Key Insight

In unweighted graphs, BFS always finds the shortest path because it explores in order of distance!

📡 Network Delay Time

The Signal Race

Story Time: You’re a network engineer. You send a signal from one computer. How long until ALL computers receive it?

This is exactly Dijkstra’s Algorithm finding the maximum of all shortest paths!

The Problem

Given:

• N computers (nodes)
• Connections with delay times (weighted edges)
• Starting computer K

Find: Time for signal to reach ALL computers

Visual Example

graph LR
    K["📡 Source"] -->|2| A
    K -->|1| B
    A -->|1| C
    B -->|1| C

Shortest paths from K:

• K → A = 2
• K → B = 1
• K → C = min(2+1, 1+1) = 2

Answer: Maximum = 2 (time for ALL to receive)

JavaScript Code

function networkDelay(times, n, k) {
  const graph = {};
  for (let i = 1; i <= n; i++) {
    graph[i] = [];
  }
  for (let [u, v, w] of times) {
    graph[u].push([v, w]);
  }

  const dist = dijkstra(graph, k);

  let maxTime = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    maxTime = Math.max(maxTime, dist[i]);
  }
  return maxTime;
}

✈️ Cheapest Flights Within K Stops

The Budget Traveler

Story Time: You want to fly from city A to city B. But you’re on a budget AND you can only take K connecting flights!

This is a modified Bellman-Ford — we relax edges only K+1 times!

Why It’s Special

• Regular shortest path: Find cheapest route (any stops)
• This problem: Find cheapest route with at most K stops

The Trick

We can take at most K+1 flights total
(K stops = K+1 flights)

So we run Bellman-Ford for exactly K+1 rounds!

JavaScript Code

function findCheapest(n, flights, src, dst, k) {
  let prices = Array(n).fill(Infinity);
  prices[src] = 0;

  // K stops = K+1 edges max
  for (let i = 0; i <= k; i++) {
    const temp = [...prices];
    for (let [from, to, price] of flights) {
      if (prices[from] !== Infinity) {
        temp[to] = Math.min(
          temp[to],
          prices[from] + price
        );
      }
    }
    prices = temp;
  }

  return prices[dst] === Infinity
    ? -1
    : prices[dst];
}

🎯 Key Insight

We use a copy of prices each round so we don’t use paths with too many edges!

🔲 Shortest Path in Binary Matrix

The Grid Navigator

Story Time: Imagine a grid of squares. Some are blocked (1), some are open (0). You start at the top-left and want to reach the bottom-right. What’s the shortest path?

Rules of the Game

• Move in 8 directions (including diagonals!)
• Can only step on 0s (open cells)
• Each step counts as 1

[0, 0, 0]    Start: top-left
[1, 1, 0]    End: bottom-right
[1, 1, 0]

The Solution: BFS

Since all steps cost 1, we use BFS!

graph TD
    S["Start 0,0"] --> A["0,1"]
    S --> B["1,1 blocked!"]
    A --> C["0,2"]
    C --> D["1,2"]
    D --> E["2,2 Goal!"]

JavaScript Code

function shortestPathBinary(grid) {
  const n = grid.length;
  if (grid[0][0] === 1) return -1;
  if (n === 1) return 1;

  const dirs = [
    [-1,-1],[-1,0],[-1,1],
    [0,-1],        [0,1],
    [1,-1], [1,0], [1,1]
  ];

  const queue = [[0, 0, 1]];
  grid[0][0] = 1; // Mark visited

  while (queue.length > 0) {
    const [r, c, dist] = queue.shift();

    for (let [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr < 0 || nr >= n) continue;
      if (nc < 0 || nc >= n) continue;
      if (grid[nr][nc] === 1) continue;

      if (nr === n-1 && nc === n-1) {
        return dist + 1;
      }

      grid[nr][nc] = 1;
      queue.push([nr, nc, dist + 1]);
    }
  }
  return -1;
}

🎓 Summary: Which Algorithm to Use?

🚀 You Did It!

You now understand the 6 essential shortest path techniques:

1. ✅ Dijkstra — The greedy explorer
2. ✅ Bellman-Ford — The patient detective
3. ✅ BFS for Unweighted — The simple walker
4. ✅ Network Delay — Maximum of minimums
5. ✅ K Stops — Budget Bellman-Ford
6. ✅ Binary Matrix — 8-direction BFS

These algorithms power GPS navigation, network routing, game AI, and so much more.

Remember: When you need the shortest path, you now have the tools. Choose wisely based on your graph’s properties! 🗺️