Shortest Path

🗺️ Finding the Shortest Path: A Journey Through Graph Algorithms

Imagine you’re a delivery driver in a big city. Every day, you need to find the quickest route to deliver packages. That’s exactly what shortest path algorithms do—they help computers find the best way to get from point A to point B!

🌟 The Big Picture

Think of a city map. Streets connect different places (called nodes or vertices). Some streets are longer, some shorter. Some have traffic, some don’t. Shortest path algorithms are like super-smart GPS systems that find the best route for you.

Our Analogy: Think of each algorithm as a different type of explorer:

• 🚗 Dijkstra = A careful driver who always picks the safest, shortest roads
• 🦸 Bellman-Ford = A superhero who can handle tricky roads (even shortcuts that go backward!)
• 🏃 BFS for Unweighted = A runner who counts steps, not distance
• 📡 Network Delay = A message traveling through the internet
• ✈️ Cheapest Flights = A budget traveler with limited stops
• 🔲 Binary Matrix = A maze walker finding the exit

1️⃣ Dijkstra’s Algorithm

🎯 What is it?

Dijkstra’s Algorithm finds the shortest path from one starting point to all other points in a graph. It’s like having a GPS that tells you the fastest route to every location in your city!

🧒 Simple Explanation

Imagine you’re at your house and want to visit all your friends. You start by visiting the closest friend first. From there, you check: “Who’s the next closest friend I haven’t visited yet?” You keep doing this until you’ve visited everyone.

🔑 Key Rules

1. Start at your home (the source)
2. Look at all places you can reach
3. Pick the closest one
4. Update distances to neighbors
5. Repeat until done!

📝 Python Example

import heapq

def dijkstra(graph, start):
    # distances to all nodes
    dist = {node: float('inf')
            for node in graph}
    dist[start] = 0

    # priority queue: (distance, node)
    pq = [(0, start)]

    while pq:
        d, node = heapq.heappop(pq)

        if d > dist[node]:
            continue

        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq,
                    (new_dist, neighbor))

    return dist

🎨 How It Works (Visual Flow)

graph TD
    A["Start at Source"] --> B["Mark distance = 0"]
    B --> C["Add to priority queue"]
    C --> D{Queue empty?}
    D -->|No| E["Pop smallest distance"]
    E --> F["Update neighbor distances"]
    F --> C
    D -->|Yes| G["Done! All shortest paths found"]

⚠️ Important Limitation

Dijkstra ONLY works with positive edge weights! If you have negative weights (like discounts or time bonuses), you need Bellman-Ford instead.

2️⃣ Bellman-Ford Algorithm

🎯 What is it?

Bellman-Ford is like Dijkstra’s superhero cousin. It can handle negative edge weights and can detect if there’s a never-ending discount loop (negative cycle)!

🧒 Simple Explanation

Imagine a store with weird pricing:

• Walking from A to B costs $5
• But walking from B to C gives you $3 back (negative weight!)

Bellman-Ford handles these tricky situations. It checks every path multiple times to make sure it found the true shortest distance.

🔑 Key Rules

1. Start with all distances as infinity
2. Set start distance to 0
3. Relax ALL edges (V-1) times
4. Check for negative cycles

📝 Python Example

def bellman_ford(n, edges, start):
    dist = [float('inf')] * n
    dist[start] = 0

    # Relax edges (n-1) times
    for _ in range(n - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf'):
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight

    # Check negative cycle
    for u, v, weight in edges:
        if dist[u] != float('inf'):
            if dist[u] + weight < dist[v]:
                return None  # Negative cycle!

    return dist

🎨 Visual Flow

graph TD
    A["Initialize distances"] --> B["Set source = 0"]
    B --> C["Repeat V-1 times"]
    C --> D["Relax ALL edges"]
    D --> E{More iterations?}
    E -->|Yes| C
    E -->|No| F["Check negative cycle"]
    F --> G{Cycle found?}
    G -->|Yes| H["Return Error"]
    G -->|No| I["Return distances"]

⚡ Dijkstra vs Bellman-Ford

3️⃣ Shortest Path in Unweighted Graph

🎯 What is it?

When all roads are equal length (weight = 1), we don’t need fancy algorithms. Simple BFS (Breadth-First Search) finds the shortest path by counting steps!

🧒 Simple Explanation

Imagine you’re playing a board game. Every square you move counts as one step. To find the shortest path, just count how many squares you need to cross. BFS explores level by level, like ripples in water.

📝 Python Example

from collections import deque

def shortest_path_bfs(graph, start, end):
    queue = deque([(start, 0)])
    visited = {start}

    while queue:
        node, dist = queue.popleft()

        if node == end:
            return dist

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(
                    (neighbor, dist + 1))

    return -1  # No path found

🎨 Visual: BFS Spreading Like Ripples

graph TD
    S["Source: Distance 0"] --> A["Level 1: Distance 1"]
    S --> B["Level 1: Distance 1"]
    A --> C["Level 2: Distance 2"]
    A --> D["Level 2: Distance 2"]
    B --> E["Level 2: Distance 2"]
    C --> F["Level 3: Distance 3"]

4️⃣ Network Delay Time

🎯 What is it?

Imagine you send a message from your computer to all other computers in a network. Network Delay Time tells you how long until EVERY computer receives the message.

🧒 Simple Explanation

Think of a group phone call. You call your best friend, who calls their friends, who call their friends. The “network delay” is when the LAST person finally gets the message. We want to find out: “How long until everyone knows?”

🔑 The Problem

Given:

• N computers (nodes)
• Times to send between computers (weighted edges)
• Starting computer K

Find: Time for ALL computers to receive the message

📝 Python Example

import heapq

def network_delay(times, n, k):
    # Build graph
    graph = {i: [] for i in range(1, n+1)}
    for u, v, w in times:
        graph[u].append((v, w))

    # Dijkstra from source k
    dist = {i: float('inf')
            for i in range(1, n+1)}
    dist[k] = 0
    pq = [(0, k)]

    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue
        for nei, time in graph[node]:
            if d + time < dist[nei]:
                dist[nei] = d + time
                heapq.heappush(pq,
                    (dist[nei], nei))

    max_time = max(dist.values())
    return max_time if max_time < float('inf') else -1

💡 Key Insight

The answer is the MAXIMUM of all shortest paths. Why? Because we need EVERYONE to receive the message. The slowest path determines the total time.

5️⃣ Cheapest Flights Within K Stops

🎯 What is it?

You want to fly from city A to city B, but you can only take at most K connecting flights. Find the cheapest way to get there!

🧒 Simple Explanation

Imagine flying from New York to Tokyo. Direct flights cost $2000. But if you stop in London and then Dubai (2 stops), it might cost only $900! This problem finds the cheapest route with a limit on stops.

🔑 The Trick

We use a modified BFS/Dijkstra that tracks:

• Current city
• Cost so far
• Number of stops used

📝 Python Example

from collections import deque

def find_cheapest_price(n, flights, src, dst, k):
    graph = {i: [] for i in range(n)}
    for u, v, price in flights:
        graph[u].append((v, price))

    # dist[node] = minimum cost to reach
    dist = [float('inf')] * n
    dist[src] = 0

    # BFS with stops limit
    queue = deque([(src, 0, 0)])
    # (node, cost, stops)

    while queue:
        node, cost, stops = queue.popleft()

        if stops > k:
            continue

        for nei, price in graph[node]:
            new_cost = cost + price
            if new_cost < dist[nei]:
                dist[nei] = new_cost
                queue.append(
                    (nei, new_cost, stops + 1))

    return dist[dst] if dist[dst] < float('inf') else -1

🎨 Visual Example

graph TD
    NYC["New York"] -->|$500| LON["London"]
    NYC -->|$2000| TYO["Tokyo"]
    LON -->|$400| DXB["Dubai"]
    DXB -->|$300| TYO
    LON -->|$800| TYO

With K=2 stops: NYC → London → Dubai → Tokyo = $1200 ✅

6️⃣ Shortest Path in Binary Matrix

🎯 What is it?

You have a grid of 0s and 1s. You can walk on 0s but not on 1s. Find the shortest path from top-left to bottom-right. You can move in 8 directions (including diagonals)!

🧒 Simple Explanation

Imagine a maze made of black (1) and white (0) tiles. You can only step on white tiles. Find the shortest way from the entrance (top-left) to the exit (bottom-right). You can walk diagonally too!

📝 Python Example

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)

    # Check if start/end is blocked
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    # 8 directions
    dirs = [(-1,-1),(-1,0),(-1,1),
            (0,-1),        (0,1),
            (1,-1), (1,0), (1,1)]

    queue = deque([(0, 0, 1)])
    # (row, col, distance)
    grid[0][0] = 1  # mark visited

    while queue:
        r, c, dist = queue.popleft()

        if r == n-1 and c == n-1:
            return dist

        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n:
                if grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    queue.append(
                        (nr, nc, dist + 1))

    return -1

🎨 8-Direction Movement

graph LR
    C["Current Cell"] --> NW["↖ Northwest"]
    C --> N["↑ North"]
    C --> NE["↗ Northeast"]
    C --> W["← West"]
    C --> E["→ East"]
    C --> SW["↙ Southwest"]
    C --> S["↓ South"]
    C --> SE["↘ Southeast"]

🏆 Algorithm Comparison Chart

🎯 Quick Decision Guide

graph TD
    A["What type of graph?"] --> B{Weighted?}
    B -->|No - All edges equal| C["Use BFS"]
    B -->|Yes| D{Negative weights?}
    D -->|No| E["Use Dijkstra"]
    D -->|Yes| F["Use Bellman-Ford"]

    G{Special constraints?} --> H{Limited stops?}
    H -->|Yes| I["Modified BFS with stop tracking"]
    G --> J{Grid/Matrix?}
    J -->|Yes| K["BFS with directions"]
    G --> L{Find max of shortest?}
    L -->|Yes| M["Dijkstra + take maximum"]

🚀 You’ve Got This!

Now you understand the six essential shortest path algorithms:

1. Dijkstra - Your go-to for positive weights
2. Bellman-Ford - The superhero for negative weights
3. BFS - Simple and elegant for unweighted graphs
4. Network Delay - Finding when everyone gets the message
5. Cheapest Flights - Budget travel with stop limits
6. Binary Matrix - Navigating grid mazes

Remember: Every algorithm is just a different strategy to explore a map. Pick the right explorer for your journey, and you’ll always find the shortest path! 🗺️✨