Shortest Path Algorithms

Introduction to Shortest Path Problems

Have you ever wondered how Google Maps calculates the fastest route to your destination in milliseconds, even when considering millions of possible paths? Or how online games determine the optimal movement path for AI characters navigating complex terrains? These everyday marvels rely on shortest path algorithms—a fundamental class of graph algorithms that you'll encounter repeatedly in technical interviews and real-world software development. In this comprehensive lesson, complete with free flashcards to reinforce your learning, we'll explore the core algorithms that power these solutions and teach you when and how to apply each one.

The beauty of shortest path problems lies in their universality. Whether you're routing network packets across the internet, planning delivery routes for a logistics company, or solving maze puzzles, you're essentially asking the same question: What's the most efficient way to get from point A to point B? Understanding these algorithms doesn't just help you ace LeetCode problems—it gives you the mental toolkit to recognize and solve optimization challenges across countless domains.

Why Shortest Path Algorithms Matter

Before diving into specific algorithms, let's understand why this topic deserves your focused attention. Shortest path algorithms represent a perfect intersection of theoretical computer science and practical engineering. They're tested extensively in technical interviews because they reveal how you think about:

🎯 Trade-offs: Different algorithms optimize for different constraints (time vs. space, positive vs. negative weights)

🎯 Problem decomposition: Breaking down complex navigation into manageable subproblems

🎯 Data structure selection: Choosing the right tools (heaps, queues, arrays) for optimal performance

🎯 Edge case handling: Dealing with negative cycles, disconnected graphs, and impossible paths

💡 Real-World Example: When Uber calculates your ride's ETA, it's not just finding the shortest distance—it's solving a weighted shortest path problem where edge weights represent estimated travel time based on current traffic, road speeds, and historical patterns. The algorithm must process this data for thousands of concurrent users while considering dynamic weight updates as traffic conditions change.

The Landscape of Shortest Path Problems

Not all shortest path problems are created equal. Understanding the problem variants helps you select the right algorithmic approach:

Single-Source Shortest Path (SSSP): Find the shortest path from one source vertex to all other vertices in the graph. This is the most common variant you'll encounter.

Example: Finding distances from your home to all restaurants in your city
Input: Graph G, starting vertex s
Output: Distance from s to every other vertex

Single-Pair Shortest Path: Find the shortest path between two specific vertices. While no algorithm is asymptotically faster than solving SSSP, you can often terminate early once you've found your target.

All-Pairs Shortest Path (APSP): Find shortest paths between every pair of vertices. Essential when you need a complete distance matrix.

Example: Computing travel times between all pairs of airports
Input: Graph G with n vertices  
Output: n×n matrix where entry (i,j) = shortest distance from i to j

Unweighted vs. Weighted Graphs: In unweighted graphs, all edges have equal cost (weight = 1), simplifying the problem significantly. Weighted graphs assign different costs to edges, requiring more sophisticated algorithms.

Non-negative vs. Negative Weights: Some algorithms only work correctly when all edge weights are non-negative. Others can handle negative weights but may fail with negative cycles (loops where the total weight is negative, making the shortest path undefined).

The Algorithm Arsenal: When to Use What

Let's preview the four major algorithms you'll master in this lesson and understand their sweet spots:

Breadth-First Search (BFS)

Best for: Unweighted graphs, finding shortest path by number of edges

Key characteristics:

• ✅ Simplest to implement
• ✅ Optimal for unweighted graphs
• ✅ Explores vertices level by level
• ❌ Cannot handle weighted graphs correctly

💡 Mental Model: Think of BFS as ripples spreading out from a stone dropped in water. Each "ripple" represents vertices at the same distance from the source.

from collections import deque

def bfs_shortest_path(graph, start, end):
    """
    Find shortest path in unweighted graph using BFS.
    Returns distance from start to end, or -1 if unreachable.
    """
    queue = deque([start])
    visited = {start}
    distance = {start: 0}
    
    while queue:
        node = queue.popleft()
        
        # Found target - BFS guarantees this is shortest path
        if node == end:
            return distance[node]
        
        # Explore neighbors
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    
    return -1  # No path exists

## Example usage: social network (unweighted)
graph = {
    'Alice': ['Bob', 'Carol'],
    'Bob': ['Alice', 'David'],
    'Carol': ['Alice', 'David', 'Eve'],
    'David': ['Bob', 'Carol'],
    'Eve': ['Carol']
}

print(bfs_shortest_path(graph, 'Alice', 'Eve'))  # Output: 2

🎯 Key Principle: BFS finds the shortest path in unweighted graphs because it explores vertices in increasing order of distance from the source. The first time you reach a vertex is guaranteed to be via the shortest path.

Dijkstra's Algorithm

Best for: Weighted graphs with non-negative edge weights

Key characteristics:

• ✅ Handles weighted graphs efficiently
• ✅ Optimal for non-negative weights
• ✅ Can terminate early when target is found
• ❌ Fails with negative edge weights
• ❌ More complex than BFS

💡 Pro Tip: Dijkstra's algorithm is essentially a greedy algorithm—it always picks the closest unvisited vertex next, assuming that once you've found the shortest path to a vertex, you'll never find a shorter one (which is true only for non-negative weights).

import heapq

def dijkstra(graph, start):
    """
    Find shortest paths from start to all vertices.
    graph: dict of {node: [(neighbor, weight), ...]}
    Returns: dict of {node: shortest_distance_from_start}
    """
    # Priority queue: (distance, node)
    pq = [(0, start)]
    distances = {start: 0}
    visited = set()
    
    while pq:
        current_dist, node = heapq.heappop(pq)
        
        # Skip if already processed (duplicate in queue)
        if node in visited:
            continue
        visited.add(node)
        
        # Explore neighbors
        for neighbor, weight in graph[node]:
            distance = current_dist + weight
            
            # Found shorter path to neighbor
            if neighbor not in distances or distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

## Example: City road network with travel times (minutes)
city_graph = {
    'Home': [('Cafe', 5), ('Park', 10)],
    'Cafe': [('Home', 5), ('Work', 15), ('Park', 8)],
    'Park': [('Home', 10), ('Cafe', 8), ('Work', 7)],
    'Work': [('Cafe', 15), ('Park', 7)]
}

print(dijkstra(city_graph, 'Home'))  
## Output: {'Home': 0, 'Cafe': 5, 'Park': 10, 'Work': 17}

⚠️ Common Mistake: Using a regular list instead of a priority queue (heap) for Dijkstra's algorithm. This increases time complexity from O((V+E) log V) to O(V²), making it inefficient for large graphs. ⚠️

Bellman-Ford Algorithm

Best for: Graphs with negative edge weights, detecting negative cycles

Key characteristics:

• ✅ Handles negative edge weights correctly
• ✅ Can detect negative cycles
• ✅ Simpler to implement than Dijkstra
• ❌ Slower than Dijkstra: O(VE) vs O((V+E) log V)
• ❌ Cannot solve graphs with negative cycles

🤔 Did you know? The Bellman-Ford algorithm is named after Richard Bellman and Lester Ford Jr., who published it independently in the 1950s. It's a classic example of dynamic programming applied to graph problems.

def bellman_ford(graph, num_vertices, start):
    """
    Find shortest paths allowing negative weights.
    graph: list of (source, dest, weight) tuples
    Returns: distances dict, or None if negative cycle exists
    """
    # Initialize distances
    distances = {i: float('inf') for i in range(num_vertices)}
    distances[start] = 0
    
    # Relax edges V-1 times
    for _ in range(num_vertices - 1):
        for source, dest, weight in graph:
            if distances[source] != float('inf'):
                if distances[source] + weight < distances[dest]:
                    distances[dest] = distances[source] + weight
    
    # Check for negative cycles (can still relax?)
    for source, dest, weight in graph:
        if distances[source] != float('inf'):
            if distances[source] + weight < distances[dest]:
                return None  # Negative cycle detected!
    
    return distances

## Example: Currency exchange (can have negative weights)
edges = [
    (0, 1, 4),   # 0 -> 1: cost 4
    (0, 2, 5),   # 0 -> 2: cost 5
    (1, 2, -3),  # 1 -> 2: cost -3 (arbitrage opportunity!)
    (2, 3, 2),   # 2 -> 3: cost 2
]

print(bellman_ford(edges, 4, 0))  
## Output: {0: 0, 1: 4, 2: 1, 3: 3}

🧠 Mnemonic: "Bellman-Ford is for Bad weights" (negative/bad weights require Bellman-Ford)

Floyd-Warshall Algorithm

Best for: All-pairs shortest path, dense graphs, small graphs

Key characteristics:

• ✅ Computes all pairs at once
• ✅ Simple implementation (just 3 nested loops)
• ✅ Handles negative weights (but not negative cycles)
• ❌ O(V³) complexity—impractical for large graphs
• ❌ O(V²) space complexity

💡 Real-World Example: When building a distance matrix for a traveling salesman problem with 50 cities, Floyd-Warshall efficiently computes all 2,500 pairwise distances in one pass. Running Dijkstra 50 times would be less efficient here.

Algorithm Comparison: The Big Picture

Understanding the time and space complexity of each algorithm helps you make informed decisions:

📋 Quick Reference Card: Algorithm Complexity Comparison

🔧 Algorithm	⏱️ Time Complexity	💾 Space Complexity	🎯 Best Use Case	⚠️ Limitations
BFS	O(V + E)	O(V)	🔵 Unweighted graphs	❌ Cannot handle weights
Dijkstra	O((V+E) log V)	O(V)	🟢 Non-negative weights	❌ Fails with negative weights
Bellman-Ford	O(V × E)	O(V)	🟡 Negative weights	❌ Slow for large graphs
Floyd-Warshall	O(V³)	O(V²)	🟣 All-pairs, small graphs	❌ Impractical for V > 500

✅ Correct thinking: "I have a weighted graph with 10,000 vertices and non-negative weights. Dijkstra's O((V+E) log V) will be much faster than Bellman-Ford's O(VE)."

❌ Wrong thinking: "Bellman-Ford handles more cases than Dijkstra, so I should always use it." (You'd be sacrificing significant performance for capabilities you don't need.)

Decision Framework: Choosing Your Algorithm

Here's a practical decision tree to guide your algorithm selection:

                    START: Need shortest path?
                              |
                              v
                    [All pairs or single source?]
                       /                    \n                   All pairs           Single source
                      |                      |
                      v                      v
              [Graph size?]         [Edge weights?]
                /        \              /        \n            Small      Large      Unweighted  Weighted
           (<500)     (>500)         |            |
             |           |            v            v
             v           v          BFS    [Negative weights?]
      Floyd-Warshall  Run SSSP            /              \n                      V times          Yes              No
                                         |                |
                                         v                v
                                    Bellman-Ford     Dijkstra

🎯 Key Principle: Start with the simplest algorithm that meets your constraints. BFS for unweighted graphs is faster and simpler than Dijkstra. Dijkstra is faster than Bellman-Ford when weights are non-negative. Only reach for more complex algorithms when your problem demands their specific capabilities.

Understanding the Core Insight

At their heart, all shortest path algorithms share a fundamental concept: relaxation. Relaxation is the process of improving an estimate of the shortest path by considering a newly discovered route.

Think of it like finding the best flight deal. Initially, you might see a direct flight for $500. That's your first estimate. Then you discover a route with a layover costing only $350. You "relax" your estimate from $500 to $350. You keep relaxing estimates until you can't find any better deals.

Initial state:  distance[B] = ∞
Discover path:  A → B with cost 10
Relax:         distance[B] = 10

Later discover: A → C → B with cost 7
Relax again:   distance[B] = 7

The algorithms differ in how they choose which edges to relax and when:

• BFS: Relaxes all edges from vertices at distance d before distance d+1
• Dijkstra: Relaxes edges from the closest unvisited vertex (greedy choice)
• Bellman-Ford: Relaxes all edges repeatedly (V-1 times)
• Floyd-Warshall: Considers all possible intermediate vertices systematically

💡 Pro Tip: Understanding relaxation deeply helps you debug shortest path implementations. If your algorithm produces incorrect results, you're likely relaxing edges in the wrong order or not relaxing enough times.

Common Problem Patterns on LeetCode

Recognizing shortest path problems in disguise is crucial for interview success. Watch for these signal phrases:

🔍 "Minimum cost/distance/time/steps": Classic shortest path language

🔍 "Fewest edges/hops/moves": Unweighted shortest path (use BFS)

🔍 "Optimal path considering X": Weighted shortest path where X determines edge weights

🔍 "Can you reach Y from X?": Often solvable with BFS/DFS, but shortest path algorithms work too

🔍 "Grid traversal with costs": Convert grid to graph, apply appropriate algorithm

Some LeetCode problems that use shortest path algorithms:

• Network Delay Time (LC 743): Pure Dijkstra's algorithm
• Cheapest Flights Within K Stops (LC 787): Modified Dijkstra with constraints
• Shortest Path in Binary Matrix (LC 1091): BFS on grid
• Path with Maximum Probability (LC 1514): Modified Dijkstra with multiplication
• Minimum Cost to Make at Least One Valid Path (LC 1368): 0-1 BFS variant

⚠️ Common Mistake: Trying to apply shortest path algorithms to problems that actually need DFS (like finding all paths or checking connectivity). Shortest path algorithms are optimized for finding optimal routes, not exploring all possibilities. ⚠️

Building Your Intuition

As you work through the remaining sections of this lesson, keep these mental models in mind:

🧠 The Optimality Principle: Shortest path algorithms rely on the insight that shortest paths contain shortest subpaths. If the shortest path from A to C goes through B, then the A→B portion must also be the shortest path from A to B.

🧠 The Tradeoff Triangle: You're always balancing three factors—correctness (handles your edge weights), speed (time complexity), and simplicity (implementation complexity). Rarely can you optimize all three.

🧠 The Negative Weight Challenge: Negative weights break the greedy assumption that once you've found a path to a vertex, you won't find a shorter one. This is why Dijkstra fails but Bellman-Ford succeeds with negative weights.

What's Next

Now that you understand the landscape of shortest path algorithms and when to use each one, we'll dive deep into implementations. In the next section, we'll explore Dijkstra's algorithm in detail—understanding not just how to implement it, but why it works, how to optimize it, and what mistakes to avoid.

You'll learn to implement Dijkstra's with a min-heap priority queue, understand why the greedy choice is optimal, handle edge cases like disconnected graphs, and apply it to real LeetCode problems. By the end of this lesson, you'll have the confidence to recognize shortest path problems instantly and implement efficient solutions under interview pressure.

💡 Remember: Mastery comes from understanding the "why" behind each algorithm, not just memorizing implementations. As you work through the code examples ahead, constantly ask yourself: "Why does this step work? What assumption am I making? When would this break?"

Let's begin our deep dive into the algorithms that power modern pathfinding!

Dijkstra's Algorithm: Theory and Implementation

Imagine you're planning a road trip and want to find the cheapest route from your home to a destination across the country. You could explore every possible path, but that would be wildly inefficient. Dijkstra's algorithm solves this exact problem with elegant efficiency, always choosing the most promising path first—a greedy approach that guarantees finding the shortest path in graphs with non-negative edge weights.

Named after Dutch computer scientist Edsger W. Dijkstra, who conceived it in 1956, this algorithm remains one of the most important tools in a programmer's arsenal. It powers GPS navigation systems, network routing protocols, and appears frequently in technical interviews at top companies.

The Core Concept: Greedy Exploration

🎯 Key Principle: Dijkstra's algorithm maintains a set of visited nodes and always processes the unvisited node with the smallest known distance from the source. Once a node is processed, we've found its shortest path—no need to reconsider it.

The algorithm works by maintaining two key pieces of information:

🧠 Distance array: Tracks the shortest known distance from the source to each node 🔧 Priority queue (min-heap): Efficiently retrieves the next nearest unvisited node

The brilliance lies in the greedy choice: by always processing the nearest unvisited node, we can be certain that we've found its optimal path. Why? Because all edge weights are non-negative, so taking a detour through other nodes can never improve upon the direct path we've already found.

💡 Mental Model: Think of Dijkstra's algorithm like ripples spreading across water after dropping a stone. The ripples expand outward uniformly, reaching nearby points before distant ones. Similarly, Dijkstra explores the graph in order of increasing distance from the source.

Step-by-Step Algorithm Walkthrough

Let's walk through a concrete example to build intuition. Consider this weighted graph where we want to find the shortest path from node A to all other nodes:

        7
    A -----> B
    |        |
  2 |        | 1
    |        |
    v    3   v
    C -----> D
    |        |
  4 |        | 5
    |        |
    v        v
    E <----- F
        2

Initial State:

• Distance to A = 0 (our source)
• Distance to all other nodes = ∞
• Priority queue = [(0, A)]
• All nodes unvisited

Iteration 1: Process A (distance = 0)

• Update neighbor C: distance = 0 + 2 = 2
• Update neighbor B: distance = 0 + 7 = 7
• Priority queue = [(2, C), (7, B)]
• Mark A as visited

Distances: A:0, B:7, C:2, D:∞, E:∞, F:∞

Iteration 2: Process C (distance = 2)

• Update neighbor D: distance = 2 + 3 = 5
• Update neighbor E: distance = 2 + 4 = 6
• Priority queue = [(5, D), (6, E), (7, B)]
• Mark C as visited

Distances: A:0, B:7, C:2, D:5, E:6, F:∞

Iteration 3: Process D (distance = 5)

• Update neighbor B: 5 + 1 = 6 < 7, so update B to 6
• Update neighbor F: distance = 5 + 5 = 10
• Priority queue = [(6, B), (6, E), (10, F)]
• Mark D as visited

Distances: A:0, B:6, C:2, D:5, E:6, F:10

Iteration 4: Process B (distance = 6)

• No updates (B has no outgoing edges in our example)
• Priority queue = [(6, E), (10, F)]
• Mark B as visited

Iteration 5: Process E (distance = 6)

• No better path to F (would be 6 + x)
• Priority queue = [(10, F)]
• Mark E as visited

Iteration 6: Process F (distance = 10)

• No unvisited neighbors
• Priority queue = []
• Mark F as visited

Final shortest distances from A: A:0, B:6, C:2, D:5, E:6, F:10

Implementation Using Min-Heap

Now let's translate this algorithm into working code. We'll show two common implementation approaches you'll encounter in LeetCode problems.

Approach 1: Basic Priority Queue Implementation

This is the most straightforward implementation using Python's heapq module:

import heapq
from collections import defaultdict
from typing import List, Tuple

def dijkstra_basic(n: int, edges: List[Tuple[int, int, int]], source: int) -> List[int]:
    """
    Find shortest paths from source to all nodes.
    
    Args:
        n: Number of nodes (0 to n-1)
        edges: List of (from_node, to_node, weight) tuples
        source: Starting node
    
    Returns:
        List of shortest distances from source to each node
    """
    # Build adjacency list: graph[u] = [(v, weight), ...]
    graph = defaultdict(list)
    for u, v, weight in edges:
        graph[u].append((v, weight))
    
    # Initialize distances to infinity
    distances = [float('inf')] * n
    distances[source] = 0
    
    # Min-heap: (distance, node)
    min_heap = [(0, source)]
    visited = set()
    
    while min_heap:
        current_dist, u = heapq.heappop(min_heap)
        
        # Skip if already visited
        if u in visited:
            continue
        
        visited.add(u)
        
        # Check all neighbors
        for v, weight in graph[u]:
            new_dist = current_dist + weight
            
            # Only update if we found a shorter path
            if new_dist < distances[v]:
                distances[v] = new_dist
                heapq.heappush(min_heap, (new_dist, v))
    
    return distances

## Example usage
edges = [
    (0, 1, 7),  # A -> B
    (0, 2, 2),  # A -> C
    (2, 3, 3),  # C -> D
    (2, 4, 4),  # C -> E
    (3, 1, 1),  # D -> B
    (3, 5, 5),  # D -> F
    (5, 4, 2),  # F -> E
]

result = dijkstra_basic(6, edges, 0)
print(f"Shortest distances from node 0: {result}")
## Output: [0, 6, 2, 5, 6, 10]

⚠️ Common Mistake 1: Forgetting to check if a node has already been visited before processing it. Without the visited set, you might process the same node multiple times, leading to incorrect results and poor performance. ⚠️

💡 Pro Tip: Notice how we push the same node onto the heap multiple times with different distances. This is intentional! The visited set ensures we only process each node once (with its minimum distance), and we skip subsequent occurrences.

Approach 2: Optimized with Distance Checking

For competitive programming and LeetCode, this slightly optimized version is often preferred:

import heapq
from typing import List, Dict

def dijkstra_optimized(graph: Dict[int, List[Tuple[int, int]]], source: int, n: int) -> List[int]:
    """
    Optimized Dijkstra with early termination checks.
    
    Args:
        graph: Adjacency list {node: [(neighbor, weight), ...]}
        source: Starting node
        n: Total number of nodes
    
    Returns:
        Shortest distances from source
    """
    distances = [float('inf')] * n
    distances[source] = 0
    min_heap = [(0, source)]
    
    while min_heap:
        current_dist, u = heapq.heappop(min_heap)
        
        # Skip if we've already found a better path to this node
        if current_dist > distances[u]:
            continue
        
        # Explore neighbors
        for v, weight in graph.get(u, []):
            new_dist = current_dist + weight
            
            if new_dist < distances[v]:
                distances[v] = new_dist
                heapq.heappush(min_heap, (new_dist, v))
    
    return distances

The key difference here is using if current_dist > distances[u]: continue instead of maintaining a separate visited set. This is more memory-efficient and slightly faster in practice.

Approach 3: Finding a Specific Target Path

Often in LeetCode, you only need the shortest path to one specific target node:

import heapq
from typing import List, Tuple, Optional

def dijkstra_to_target(n: int, edges: List[Tuple[int, int, int]], 
                        source: int, target: int) -> Optional[int]:
    """
    Find shortest path from source to target node.
    Returns None if target is unreachable.
    """
    graph = {i: [] for i in range(n)}
    for u, v, weight in edges:
        graph[u].append((v, weight))
    
    distances = {i: float('inf') for i in range(n)}
    distances[source] = 0
    min_heap = [(0, source)]
    
    while min_heap:
        current_dist, u = heapq.heappop(min_heap)
        
        # Early termination: found shortest path to target!
        if u == target:
            return current_dist
        
        # Skip if outdated entry
        if current_dist > distances[u]:
            continue
        
        for v, weight in graph[u]:
            new_dist = current_dist + weight
            if new_dist < distances[v]:
                distances[v] = new_dist
                heapq.heappush(min_heap, (new_dist, v))
    
    # Target unreachable
    return None if distances[target] == float('inf') else distances[target]

💡 Pro Tip: The early termination when we reach the target is a significant optimization. Once we pop the target from the heap, we know we've found the shortest path to it!

Time Complexity Analysis

Understanding the time complexity of Dijkstra's algorithm is crucial for interview discussions and choosing the right algorithm.

🎯 Key Principle: The time complexity is O((V + E) log V) when using a binary heap (priority queue), where V is the number of vertices and E is the number of edges.

Let's break down where this comes from:

Operations and their costs:

Operation	Frequency	Cost per Operation	Total Cost
🔧 Push to heap	O(E)	O(log V)	O(E log V)
🔧 Pop from heap	O(V)	O(log V)	O(V log V)
🧠 Update distances	O(E)	O(1)	O(E)

Why these frequencies?

📚 Pop operations (O(V)): Each of the V vertices is popped from the heap at most once (when we process it). In practice, we might pop more due to duplicate entries, but the dominated term remains O(V log V).

📚 Push operations (O(E)): For each edge, we potentially push a node onto the heap when we discover a better path. In the worst case, this happens once per edge.

Combining these: O(V log V + E log V) = O((V + E) log V)

For dense graphs where E ≈ V², this simplifies to O(V² log V). For sparse graphs where E ≈ V, it's closer to O(V log V).

Space Complexity: O(V + E) for storing the graph plus O(V) for the distance array and heap, giving us O(V + E) overall.

🤔 Did you know? Using a Fibonacci heap instead of a binary heap can theoretically reduce the time complexity to O(E + V log V), but Fibonacci heaps have high constant factors and complex implementation, making them rarely worthwhile in practice or coding interviews.

Why Dijkstra Fails with Negative Edge Weights

This is one of the most important limitations to understand, and interviewers love asking about it.

⚠️ Common Mistake 2: Using Dijkstra's algorithm on graphs with negative edge weights. The algorithm will produce incorrect results! ⚠️

The fundamental problem: Dijkstra's correctness relies on the assumption that once we visit a node (pop it from the priority queue), we've found its shortest path. This breaks down with negative weights.

Consider this simple counter-example:

    A ---5---> B
    |          ^
    |          |
    +----1---> C
               |
              -10

What Dijkstra would do:

1. Start at A (distance = 0)
2. Process A: Update B to 5, C to 1
3. Process C (distance = 1) - mark C as visited
4. Process B (distance = 5) via the direct edge
5. Problem: We never reconsider B via the C → B path!

If there were an edge from C to B with weight -10, the actual shortest path to B would be A → C → B with total cost 1 + (-10) = -9, not the direct path of 5.

❌ Wrong thinking: "I can just check for negative weights and adjust the distances accordingly."

✅ Correct thinking: "With negative weights, I need an algorithm that continues to relax edges even after visiting nodes, like Bellman-Ford."

Why the greedy choice fails:

Dijkstra's greedy approach assumes that going through an unvisited node can't improve the path to an already-visited node. With non-negative weights, this is true: if you've found a path of cost 5, and the next nearest unvisited node is at distance 7, no path through that node can beat 5 (since you'd need at least 7 + something ≥ 0).

With negative weights, you might reach that distance-7 node and find an edge of weight -100, suddenly making it better than your distance-5 path!

💡 Remember: Dijkstra requires non-negative edge weights. If you encounter negative weights:

• Use Bellman-Ford instead (handles negative weights, detects negative cycles)
• Or use SPFA (Shortest Path Faster Algorithm) as an optimized variant
• For all-pairs shortest paths with negative weights, consider Floyd-Warshall

Practical Variations and Optimizations

In real LeetCode problems, you'll often need to adapt Dijkstra's algorithm. Here are common variations:

1. Tracking the actual path, not just distances:

def dijkstra_with_path(graph, source, target):
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
    parent = {source: None}  # Track the path
    min_heap = [(0, source)]
    
    while min_heap:
        current_dist, u = heapq.heappop(min_heap)
        
        if u == target:
            # Reconstruct path
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return current_dist, path[::-1]
        
        if current_dist > distances[u]:
            continue
        
        for v, weight in graph[u]:
            new_dist = current_dist + weight
            if new_dist < distances[v]:
                distances[v] = new_dist
                parent[v] = u  # Remember where we came from
                heapq.heappush(min_heap, (new_dist, v))
    
    return float('inf'), []  # No path exists

2. Multi-dimensional state: Sometimes the "node" in your heap isn't just a vertex, but a (vertex, state) tuple. For example, finding the shortest path where you can use up to k edges of zero cost.

3. Bidirectional Dijkstra: Run Dijkstra from both source and target simultaneously, stopping when the search frontiers meet. This can halve the search space in practice.

🧠 Mnemonic: "Dijkstra Demands Distances be Decreasing" - remember that Dijkstra processes nodes in order of increasing distance from the source, which is why negative weights break this invariant.

Summary: When to Use Dijkstra

Dijkstra's algorithm shines in specific scenarios:

✅ Use Dijkstra when:

• All edge weights are non-negative
• You need single-source shortest paths
• The graph is sparse to moderately dense
• You need fast performance for repeated queries (precompute with Dijkstra)

❌ Don't use Dijkstra when:

• Edge weights can be negative (use Bellman-Ford)
• You need all-pairs shortest paths in a dense graph (use Floyd-Warshall)
• The graph is unweighted (use BFS instead - it's simpler and faster)

📋 Quick Reference Card:

Aspect	Details
🎯 Time Complexity	O((V + E) log V)
🔒 Space Complexity	O(V + E)
✅ Handles Negative Weights	No
✅ Detects Negative Cycles	No
🔧 Key Data Structure	Min-heap (priority queue)
🧠 Algorithm Type	Greedy, single-source
📚 Best Use Case	Non-negative weighted graphs

With this solid understanding of Dijkstra's algorithm, you're equipped to tackle a wide range of shortest path problems. The key is recognizing when the greedy approach applies—when all edges point you forward, never backward, Dijkstra finds the way efficiently and elegantly.

Bellman-Ford and Handling Negative Weights

While Dijkstra's algorithm elegantly solves shortest path problems with impressive efficiency, it has a critical limitation: it cannot handle negative edge weights. This is where the Bellman-Ford algorithm steps in, offering a more versatile solution that not only handles negative weights but also detects negative cycles—a feature that makes it indispensable for certain applications.

Understanding the Need for Bellman-Ford

Imagine you're building a currency exchange system where edges represent conversion rates. Sometimes, due to market inefficiencies or fees, converting through multiple currencies might actually give you more money than you started with—a negative cycle in terms of cost. Or consider a network where edges represent changes in elevation: going downhill would be a negative weight. Dijkstra's greedy approach fails in these scenarios because it assumes once you've found the shortest path to a node, you'll never find a better one. With negative weights, this assumption breaks down.

🎯 Key Principle: Bellman-Ford trades speed for versatility. While it runs slower at O(VE) compared to Dijkstra's O(E log V), it handles negative weights and provides crucial cycle detection.

Algorithm Mechanics: The Power of Relaxation

The Bellman-Ford algorithm works through a beautifully simple principle: edge relaxation. To relax an edge means to check if going through that edge gives us a shorter path to the destination vertex than we currently know.

Here's the key insight: if the shortest path from source to any vertex uses at most k edges, then after k iterations of relaxing all edges, we'll have found that shortest path. Since the shortest simple path (one without cycles) in a graph with V vertices can have at most V-1 edges, we need to relax all edges exactly V-1 times.

💡 Mental Model: Think of it like gossip spreading through a network. In each round, every person (edge) shares the best information they have. After V-1 rounds, everyone has heard the best possible news (shortest path) if there's no negative cycle distorting reality.

Let's visualize how this works with a simple example:

Initial graph with source A:

    A ---2---> B
    |         |
    3        -4
    |         |
    v         v
    C ---1--> D

Initial distances: A=0, B=∞, C=∞, D=∞

Iteration 1 (relax all edges):
- Edge A→B: dist[B] = min(∞, 0+2) = 2
- Edge A→C: dist[C] = min(∞, 0+3) = 3
- Edge B→D: dist[D] = min(∞, 2+(-4)) = -2
- Edge C→D: dist[D] = min(-2, 3+1) = -2

Iteration 2:
- Edge A→B: dist[B] = min(2, 0+2) = 2
- Edge A→C: dist[C] = min(3, 0+3) = 3
- Edge B→D: dist[D] = min(-2, 2+(-4)) = -2
- Edge C→D: dist[D] = min(-2, 3+1) = -2

No changes in iteration 2, but we run V-1 times to guarantee correctness.

Core Implementation

The Bellman-Ford algorithm is typically implemented using an edge list representation rather than an adjacency list. This makes it straightforward to iterate through all edges repeatedly.

def bellman_ford(edges, n, source):
    """
    Finds shortest paths from source to all vertices.
    
    Args:
        edges: List of tuples (u, v, weight)
        n: Number of vertices (0 to n-1)
        source: Starting vertex
    
    Returns:
        distances: List of shortest distances from source
        None if negative cycle detected
    """
    # Step 1: Initialize distances
    distances = [float('inf')] * n
    distances[source] = 0
    
    # Step 2: Relax all edges V-1 times
    for iteration in range(n - 1):
        updated = False
        
        for u, v, weight in edges:
            # If we found a shorter path to v through u
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                updated = True
        
        # Optimization: early termination
        if not updated:
            break
    
    # Step 3: Check for negative cycles
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            return None  # Negative cycle detected
    
    return distances

## Example usage
edges = [
    (0, 1, 4),   # A -> B: 4
    (0, 2, 5),   # A -> C: 5
    (1, 2, -3),  # B -> C: -3
    (2, 3, 2),   # C -> D: 2
    (1, 3, 6)    # B -> D: 6
]

result = bellman_ford(edges, 4, 0)
print(f"Shortest distances: {result}")
## Output: [0, 4, 1, 3]

Notice the early termination optimization in the code. If during an iteration we don't update any distance, we know we've found all shortest paths and can stop early. This can significantly improve performance in practice, especially for sparse graphs or when the actual longest shortest path is much shorter than V-1 edges.

Detecting Negative Cycles: Why They Matter

A negative cycle is a cycle in the graph where the sum of edge weights is negative. This is critically important because if such a cycle is reachable from the source, there is no shortest path—you can keep going around the cycle, making the path arbitrarily short (approaching negative infinity).

Negative cycle example:

    A ---2---> B
    ^          |
    |         -5
    |          |
    +----3---- C

Cycle weight: 2 + (-5) + 3 = 0? No!
Actually: B→C: -5, C→A: 3, A→B: 2
Sum: -5 + 3 + 2 = 0 (not negative)

Actual negative cycle:

    A ---2---> B
    ^          |
    |         -6
    |          |
    +----3---- C
    
Sum: 2 + (-6) + 3 = -1 (negative cycle!)

🤔 Did you know? Negative cycle detection is used in financial systems to identify arbitrage opportunities. If you can convert currencies in a cycle and end up with more money than you started, you've found a profitable arbitrage—a negative cycle in the cost graph!

The detection mechanism is elegant: after V-1 iterations, all shortest paths are found (if no negative cycle exists). If we can still relax any edge on the Vth iteration, it means we're finding shorter paths even after V-1 edges, which is only possible if we're going around a negative cycle.

⚠️ Common Mistake 1: Forgetting to check if the source vertex distance is infinity before relaxing. If distances[u] is infinity, adding the weight will still give infinity, not a valid path. ⚠️

⚠️ Common Mistake 2: Only running V-2 iterations instead of V-1. Remember, a path can have up to V-1 edges! ⚠️

LeetCode-Style Implementation with Path Reconstruction

In many problems, you need not just the shortest distance but the actual path. Here's an enhanced implementation that tracks predecessors:

def bellman_ford_with_path(edges, n, source, target):
    """
    Finds shortest path from source to target with path reconstruction.
    
    Returns:
        (distance, path) or (None, None) if negative cycle or no path
    """
    distances = [float('inf')] * n
    predecessors = [-1] * n
    distances[source] = 0
    
    # Relax edges V-1 times
    for _ in range(n - 1):
        updated = False
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                predecessors[v] = u
                updated = True
        
        if not updated:
            break
    
    # Check for negative cycles
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            return None, None  # Negative cycle detected
    
    # Reconstruct path
    if distances[target] == float('inf'):
        return None, None  # No path exists
    
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = predecessors[current]
    path.reverse()
    
    return distances[target], path

## Example: Find path from vertex 0 to vertex 3
edges = [
    (0, 1, 1),
    (1, 2, -2),
    (2, 3, 3),
    (0, 2, 4)
]

dist, path = bellman_ford_with_path(edges, 4, 0, 3)
print(f"Distance: {dist}, Path: {path}")
## Output: Distance: 2, Path: [0, 1, 2, 3]

When to Choose Bellman-Ford Over Dijkstra

The decision between these algorithms depends on your graph's properties and requirements:

📋 Quick Reference Card:

Factor	Bellman-Ford	Dijkstra
🔢 Time Complexity	O(VE)	O(E log V) with heap
➖ Negative Weights	✅ Handles them	❌ Fails or incorrect
🔄 Cycle Detection	✅ Detects negative cycles	❌ No cycle detection
📊 Graph Density	Better for dense graphs	Better for sparse graphs
🎯 Use Case	Currency exchange, networks with costs	Road networks, positive weights
🚀 Performance	Slower but versatile	Faster but restricted

💡 Pro Tip: For LeetCode problems, look for these keywords that signal Bellman-Ford: "may contain negative weights," "detect negative cycle," "arbitrage," or "at most K edges." The K-edges variant is particularly common and requires a modified Bellman-Ford.

The K-Edges Variant: Cheapest Flights Within K Stops

A popular LeetCode pattern modifies Bellman-Ford to find shortest paths using at most K edges. This appears in problems like "Cheapest Flights Within K Stops" (LeetCode 787).

def findCheapestPrice(n, flights, src, dst, k):
    """
    Find cheapest price from src to dst with at most k stops.
    k stops means k+1 edges!
    
    Args:
        n: Number of cities
        flights: List of [from, to, price]
        src: Source city
        dst: Destination city
        k: Maximum number of stops
    
    Returns:
        Minimum price or -1 if impossible
    """
    # Initialize distances
    prices = [float('inf')] * n
    prices[src] = 0
    
    # Run k+1 iterations (k stops = k+1 edges)
    for _ in range(k + 1):
        # IMPORTANT: Use a temporary array to avoid using updated values
        # within the same iteration
        temp_prices = prices.copy()
        
        for u, v, price in flights:
            if prices[u] != float('inf'):
                temp_prices[v] = min(temp_prices[v], prices[u] + price)
        
        prices = temp_prices
    
    return prices[dst] if prices[dst] != float('inf') else -1

## Example
flights = [[0,1,100],[1,2,100],[0,2,500]]
result = findCheapestPrice(3, flights, 0, 2, 1)
print(f"Cheapest price: {result}")
## Output: 200 (path 0->1->2)

⚠️ Common Mistake 3: In the K-edges variant, using the same array for reading and writing within an iteration. This allows a vertex to be updated multiple times in one iteration, effectively using more edges than intended. Always use a temporary array! ⚠️

Optimization Techniques

Beyond early termination, several optimizations can improve Bellman-Ford's practical performance:

🔧 Queue-Based Optimization (SPFA): The Shortest Path Faster Algorithm (SPFA) uses a queue to only process edges from vertices that were updated in the previous iteration. This can reduce the average-case complexity significantly:

from collections import deque

def spfa(graph, n, source):
    """
    SPFA optimization of Bellman-Ford using a queue.
    graph: adjacency list {u: [(v, weight), ...]}
    """
    distances = [float('inf')] * n
    distances[source] = 0
    
    queue = deque([source])
    in_queue = [False] * n
    in_queue[source] = True
    count = [0] * n  # Count of times each vertex is enqueued
    
    while queue:
        u = queue.popleft()
        in_queue[u] = False
        
        for v, weight in graph.get(u, []):
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
                    count[v] += 1
                    
                    # Negative cycle detection
                    if count[v] >= n:
                        return None
    
    return distances

💡 Remember: SPFA has better average-case performance but the same worst-case O(VE) complexity. It's particularly effective on sparse graphs where most vertices don't update in each iteration.

Real-World Applications

🌍 Real-World Example: Network routing protocols like RIP (Routing Information Protocol) use a distance-vector algorithm based on Bellman-Ford. Routers exchange information about the distance to various networks, updating their routing tables through edge relaxation. The "count to infinity" problem in RIP is essentially a negative cycle issue!

Other applications include:

• 🏦 Financial arbitrage detection in currency markets
• 🗺️ Navigation with toll roads where tolls might be negative (discounts/rebates)
• ⚡ Circuit analysis with voltage gains and drops
• 🎮 Game AI pathfinding with terrain costs that might reduce resource consumption

Comparing Performance: When Does Bellman-Ford Win?

While Dijkstra is faster in most scenarios, Bellman-Ford can be competitive or even superior when:

✅ Correct thinking: "The graph is very dense (E approaches V²) and I need to detect negative cycles. Bellman-Ford's O(V³) becomes acceptable, and Dijkstra can't handle negative weights anyway."

❌ Wrong thinking: "Bellman-Ford is always slower, so I should try to convert negative weights to positive ones." (This usually doesn't preserve shortest paths!)

🧠 Mnemonic: Bellman-Ford handles Bad (negative) weights and Finds negative cycles. Dijkstra is Definitely faster but Doesn't handle negatives.

Implementation Checklist for LeetCode

When implementing Bellman-Ford on LeetCode, follow this checklist:

• ✅ Initialize distances array with infinity except source (0)
• ✅ Run exactly V-1 iterations for standard shortest path
• ✅ Check distances[u] != float('inf') before relaxing from u
• ✅ Use temporary array for K-edges variant
• ✅ Add negative cycle detection if problem requires it
• ✅ Consider early termination optimization
• ✅ Handle unreachable vertices (distance still infinity)
• ✅ Reconstruct path if needed using predecessor array

Summary

The Bellman-Ford algorithm is your tool of choice when dealing with negative edge weights or when you need to detect negative cycles. While it sacrifices the speed of Dijkstra's greedy approach, it gains the reliability and versatility needed for more complex graph scenarios. Understanding when and how to apply Bellman-Ford—including its optimizations like SPFA and the K-edges variant—is crucial for tackling a wide range of LeetCode problems and real-world applications.

The key is recognizing the trade-off: O(VE) time complexity for the ability to handle negative weights and detect cycles that would break other algorithms. In the next section, we'll see how to recognize which algorithm to apply when facing practical LeetCode problems, combining our knowledge of both Dijkstra and Bellman-Ford to choose the right tool for each situation.

Practical LeetCode Implementation Patterns

Now that we understand the theoretical foundations of shortest path algorithms, let's translate that knowledge into patterns you'll encounter repeatedly on LeetCode and in technical interviews. The key to mastering these problems isn't just memorizing algorithms—it's recognizing problem patterns and knowing which algorithmic approach fits each situation.

Pattern 1: Grid-Based Shortest Path Problems

One of the most common patterns you'll encounter transforms a 2D grid into an implicit graph. Each cell becomes a node, and adjacent cells (up, down, left, right, and sometimes diagonals) represent edges. This pattern appears in maze problems, robot navigation, and terrain traversal challenges.

🎯 Key Principle: When you see a 2D grid where you need to find the shortest path, minimum steps, or optimal route, you're dealing with a graph problem in disguise.

Let's examine the foundational template for grid-based problems:

from collections import deque
from typing import List

def shortestPathBinaryMatrix(grid: List[List[int]]) -> int:
    """
    LeetCode 1091: Shortest Path in Binary Matrix
    Find shortest path from top-left to bottom-right in a binary grid.
    Can move in 8 directions (including diagonals).
    """
    if grid[0][0] == 1 or grid[-1][-1] == 1:
        return -1
    
    n = len(grid)
    if n == 1:
        return 1
    
    # BFS for unweighted grid = shortest path
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    grid[0][0] = 1  # Mark as visited
    
    # 8 directions: up, down, left, right, and 4 diagonals
    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), 
                  (0,1), (1,-1), (1,0), (1,1)]
    
    while queue:
        row, col, dist = queue.popleft()
        
        # Explore all 8 neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check boundaries and if cell is accessible
            if (0 <= new_row < n and 0 <= new_col < n and 
                grid[new_row][new_col] == 0):
                
                # Found destination
                if new_row == n-1 and new_col == n-1:
                    return dist + 1
                
                # Mark as visited and add to queue
                grid[new_row][new_col] = 1
                queue.append((new_row, new_col, dist + 1))
    
    return -1  # No path exists

This template demonstrates several critical patterns:

Pattern Recognition: When all edges have equal weight (each step costs 1), use BFS for the shortest path. BFS naturally explores level by level, guaranteeing that when you reach the destination, you've found the shortest path.

State Representation: The tuple (row, col, distance) encodes everything needed to track our position and path length. This is the state in our graph traversal.

Visited Tracking: We modify the grid itself (grid[new_row][new_col] = 1) to mark visited cells. This prevents revisiting and infinite loops.

⚠️ Common Mistake: Forgetting to check if the start or end position is blocked before beginning the search. This causes unnecessary computation. ⚠️

💡 Pro Tip: For grid problems with uniform costs, always reach for BFS first. It's simpler and faster than Dijkstra's algorithm when edge weights are equal.

Now let's look at a variation where cells have different weights:

import heapq
from typing import List

def minPathSum(grid: List[List[int]]) -> int:
    """
    LeetCode 64: Minimum Path Sum
    Find path from top-left to bottom-right with minimum sum.
    Can only move right or down.
    """
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    
    # Dijkstra's algorithm with min-heap
    # (cost, row, col)
    heap = [(grid[0][0], 0, 0)]
    visited = set()
    
    while heap:
        cost, row, col = heapq.heappop(heap)
        
        # Reached destination
        if row == rows - 1 and col == cols - 1:
            return cost
        
        # Skip if already visited
        if (row, col) in visited:
            continue
        visited.add((row, col))
        
        # Explore neighbors (right and down only)
        for dr, dc in [(0, 1), (1, 0)]:
            new_row, new_col = row + dr, col + dc
            
            if (0 <= new_row < rows and 0 <= new_col < cols and 
                (new_row, new_col) not in visited):
                
                new_cost = cost + grid[new_row][new_col]
                heapq.heappush(heap, (new_cost, new_row, new_col))
    
    return -1  # Should never reach here if grid is valid

This example illustrates when to upgrade from BFS to Dijkstra's algorithm. Because each cell has a different value (weight), we need Dijkstra's greedy approach with a min-heap to always explore the lowest-cost path first.

Grid visualization:
┌───┬───┬───┐       Path options:
│ 1 │ 3 │ 1 │       
├───┼───┼───┤       1 → 3 → 1 → 1 = 6
│ 1 │ 5 │ 1 │       1 → 1 → 1 → 1 = 4 ✓ (minimum)
├───┼───┼───┤
│ 4 │ 2 │ 1 │
└───┴───┴───┘

Pattern 2: Network Delay Time and Graph Connectivity

The network delay problem represents a classic application of shortest path algorithms where you have an explicit graph with weighted edges. This pattern appears in problems involving signal propagation, network routing, and dependency resolution.

🎯 Key Principle: When you need to find "time for all nodes to receive a signal" or "minimum time to reach all destinations," think Dijkstra's algorithm.

Here's the canonical template:

import heapq
from collections import defaultdict
from typing import List

def networkDelayTime(times: List[List[int]], n: int, k: int) -> int:
    """
    LeetCode 743: Network Delay Time
    times[i] = (source, target, time)
    Find minimum time for all n nodes to receive signal from node k.
    """
    # Build adjacency list: node -> [(neighbor, weight)]
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    # Dijkstra's algorithm
    # (time, node)
    min_heap = [(0, k)]  # Start from node k with time 0
    distances = {}  # node -> minimum time to reach it
    
    while min_heap:
        time, node = heapq.heappop(min_heap)
        
        # Skip if we've already found a better path to this node
        if node in distances:
            continue
        
        # Record the minimum time to reach this node
        distances[node] = time
        
        # Explore neighbors
        for neighbor, weight in graph[node]:
            if neighbor not in distances:
                heapq.heappush(min_heap, (time + weight, neighbor))
    
    # Check if all nodes are reachable
    if len(distances) != n:
        return -1
    
    # Return the maximum time (when the last node receives the signal)
    return max(distances.values())

This template showcases several important patterns:

Graph Representation: We use an adjacency list stored in a defaultdict. This is more space-efficient than an adjacency matrix for sparse graphs (graphs with relatively few edges).

Distance Tracking: The distances dictionary serves double duty—it tracks both the minimum time to each node AND acts as our visited set. Once a node is in distances, we've found its shortest path.

Result Aggregation: Notice how the answer is max(distances.values()). We need ALL nodes to receive the signal, so the answer is when the LAST node receives it.

💡 Mental Model: Think of Dijkstra's algorithm like water flowing through pipes. The water (signal) reaches closer nodes first, then gradually propagates to more distant nodes. The time when the last node gets wet is your answer.

⚠️ Common Mistake: Forgetting to check if all nodes are reachable (len(distances) != n). A disconnected graph means some nodes never receive the signal, so the answer should be -1. ⚠️

Algorithm Selection Decision Tree:

Graph problem?
    |
    ├─ Unweighted edges? → BFS
    |
    ├─ Non-negative weights? → Dijkstra
    |
    ├─ Negative weights?
    │   |
    │   ├─ Need to detect negative cycles? → Bellman-Ford
    │   └─ All-pairs shortest path? → Floyd-Warshall
    │
    └─ Grid-based?
        |
        ├─ All cells cost 1? → BFS
        └─ Cells have different costs? → Dijkstra

Pattern 3: Path with Minimum Cost/Effort Variations

A sophisticated pattern involves problems where the "cost" isn't simply the sum of edge weights—it might be the maximum edge on the path, the product of probabilities, or some other aggregation function. These problems require adapting our standard templates.

Variation A: Minimizing the Maximum (Path with Minimum Effort)

Consider LeetCode 1631: Path With Minimum Effort. You traverse a grid where the effort is the maximum absolute difference in heights between consecutive cells. This isn't a sum—it's a maximum!

import heapq
from typing import List

def minimumEffortPath(heights: List[List[int]]) -> int:
    """
    LeetCode 1631: Path With Minimum Effort
    Find path where the maximum absolute height difference is minimized.
    """
    rows, cols = len(heights), len(heights[0])
    
    # Modified Dijkstra: track maximum effort on path
    # (max_effort_so_far, row, col)
    min_heap = [(0, 0, 0)]
    efforts = [[float('inf')] * cols for _ in range(rows)]
    efforts[0][0] = 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while min_heap:
        effort, row, col = heapq.heappop(min_heap)
        
        # Reached destination
        if row == rows - 1 and col == cols - 1:
            return effort
        
        # Skip if we've found a better path
        if effort > efforts[row][col]:
            continue
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if 0 <= new_row < rows and 0 <= new_col < cols:
                # Calculate effort: max of current path effort and 
                # the effort to move to this new cell
                new_effort = max(
                    effort,
                    abs(heights[new_row][new_col] - heights[row][col])
                )
                
                # Only explore if we found a better path
                if new_effort < efforts[new_row][new_col]:
                    efforts[new_row][new_col] = new_effort
                    heapq.heappush(min_heap, (new_effort, new_row, new_col))
    
    return 0

The key insight here is the modified cost calculation:

new_effort = max(effort, abs(heights[new_row][new_col] - heights[row][col]))

Instead of adding costs (like traditional Dijkstra), we take the maximum. This finds the path where the steepest step is as gentle as possible.

💡 Pro Tip: The beauty of Dijkstra's framework is its flexibility. The greedy property holds as long as your cost function is monotonic (non-decreasing as you extend the path). Maximum, sum, and product (of values < 1) all satisfy this property.

Variation B: Path with Maximum Probability

Another fascinating variation involves maximizing instead of minimizing. In LeetCode 1514 (Path with Maximum Probability), you want the path with the highest probability of success.

🧠 Mnemonic: MAX-heap for MAX-imize, MIN-heap for MIN-imize.

The template adaptation:

import heapq
from collections import defaultdict
from typing import List

def maxProbability(n: int, edges: List[List[int]], 
                   succProb: List[float], start: int, end: int) -> float:
    """
    LeetCode 1514: Path with Maximum Probability
    Find path with highest probability of success.
    """
    # Build graph
    graph = defaultdict(list)
    for i, (u, v) in enumerate(edges):
        prob = succProb[i]
        graph[u].append((v, prob))
        graph[v].append((u, prob))
    
    # MAX-heap: use negative probabilities to simulate max-heap
    # (-probability, node)
    max_heap = [(-1.0, start)]  # Start with probability 1.0
    probabilities = {start: 1.0}
    
    while max_heap:
        prob, node = heapq.heappop(max_heap)
        prob = -prob  # Convert back to positive
        
        if node == end:
            return prob
        
        # Skip if we've found a better path
        if prob < probabilities.get(node, 0):
            continue
        
        for neighbor, edge_prob in graph[node]:
            new_prob = prob * edge_prob  # Multiply probabilities
            
            if new_prob > probabilities.get(neighbor, 0):
                probabilities[neighbor] = new_prob
                heapq.heappush(max_heap, (-new_prob, neighbor))
    
    return 0.0  # No path exists

⚠️ Common Mistake: Python's heapq only provides a min-heap. To maximize, negate the values when pushing and pop them. Don't try to multiply by -1 just once—you must negate both when pushing AND when popping. ⚠️

Code Templates and Reusable Patterns

Let's consolidate the patterns into reusable templates you can adapt quickly during interviews.

📋 Quick Reference Card: Algorithm Selection

🎯 Problem Type	🔧 Algorithm	📊 Data Structure	⏱️ Time Complexity
Unweighted grid/graph	BFS	Queue (deque)	O(V + E)
Weighted edges (non-negative)	Dijkstra	Min-heap	O((V + E) log V)
Negative edge weights	Bellman-Ford	Arrays	O(V × E)
Find all paths	Floyd-Warshall	2D array	O(V³)
Maximum probability	Modified Dijkstra	Max-heap	O((V + E) log V)

BFS Template (Unweighted):

from collections import deque

def bfs_shortest_path(start, end, graph):
    queue = deque([(start, 0)])  # (node, distance)
    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

Dijkstra Template (Weighted):

import heapq

def dijkstra_shortest_path(start, end, graph):
    # graph[node] = [(neighbor, weight), ...]
    heap = [(0, start)]  # (cost, node)
    distances = {}
    
    while heap:
        cost, node = heapq.heappop(heap)
        
        if node in distances:
            continue
        
        distances[node] = cost
        
        if node == end:
            return cost
        
        for neighbor, weight in graph[node]:
            if neighbor not in distances:
                heapq.heappush(heap, (cost + weight, neighbor))
    
    return -1  # No path found

Decision Framework: Which Algorithm to Use

Here's how to systematically identify the right approach:

Step 1: Identify the Graph Structure

🔍 Questions to ask:

• Is this explicitly a graph, or is it disguised (like a grid)?
• What are the nodes? What are the edges?
• Are edges directed or undirected?

Step 2: Analyze Edge Weights

🔍 Questions to ask:

• Are all edges equal weight? → BFS
• Are weights non-negative? → Dijkstra
• Can weights be negative? → Bellman-Ford
• Do you need all-pairs distances? → Floyd-Warshall

Step 3: Consider Problem-Specific Constraints

🔍 Questions to ask:

• What defines "cost"? (Sum? Maximum? Product?)
• Are you minimizing or maximizing?
• Is there a special grid structure with limited movement?
• Are there obstacles or forbidden states?

Step 4: Optimize Data Structures

🔍 Questions to ask:

• For grid problems: Can you modify the grid for visited tracking, or do you need a separate set?
• For sparse graphs: Use adjacency list
• For dense graphs: Consider adjacency matrix
• For limited node values: Use array instead of dictionary

💡 Real-World Example: Imagine you're building a GPS navigation system. If you only care about the number of turns (unweighted), use BFS. If you're minimizing distance with varying road lengths (weighted, non-negative), use Dijkstra. If you have toll roads that could save time (negative weights in a sense), you'd need Bellman-Ford to handle the complexity.

Advanced Pattern Recognition

Pattern: Early Termination

When you only need the shortest path to ONE specific target (not all nodes), you can terminate as soon as you pop that target from the heap:

if node == target:
    return distance  # Early termination

This optimization can save significant time in large graphs.

Pattern: Bidirectional Search

For problems where you know both start and end, consider running BFS/Dijkstra from BOTH directions simultaneously. When the searches meet, you've found the shortest path. This can reduce complexity from O(b^{d) to O(b}(d/2)) where b is branching factor and d is depth.

Pattern: State Augmentation

Sometimes you need to track MORE than just position. For example:

• Position + keys collected (in a maze with locked doors)
• Position + fuel remaining (in a limited-fuel problem)
• Position + direction facing (if turning has a cost)

The pattern is to expand your state tuple to include all relevant information:

## Instead of: (cost, row, col)
## Use: (cost, row, col, keys_collected)
heap = [(0, start_row, start_col, frozenset())]

🤔 Did you know? The A* algorithm extends Dijkstra by adding a heuristic function that estimates remaining distance to the goal. This guides the search more efficiently toward the target. While less common in basic LeetCode problems, it's the foundation of pathfinding in games and robotics!

Putting It All Together

Mastering these patterns means recognizing that most LeetCode shortest path problems are variations on a few core themes:

✅ Grid → Graph: Cells are nodes, adjacency is edges ✅ Network Propagation: Classic Dijkstra on explicit graph ✅ Cost Variations: Modify the aggregation function (max, product, etc.) ✅ Optimization: Early termination, bidirectional search, state augmentation

The key is pattern recognition. When you see a new problem, ask:

1. What's the graph structure?
2. What are the edge weights?
3. What defines the cost?
4. Am I minimizing or maximizing?

With these questions answered, you can select the right template and adapt it to the specific constraints. The algorithms are tools—your job is to recognize which tool fits the problem at hand.

💡 Remember: In interviews, it's often better to start with a working BFS solution and then optimize to Dijkstra if needed, rather than jumping straight to the more complex algorithm. Show your thought process and build incrementally!

Common Pitfalls and Optimization Techniques

You've learned the theory behind shortest path algorithms and seen them work in practice. Now it's time to level up your implementation skills by understanding the subtle mistakes that can tank your solution's performance and learning the optimization techniques that separate good code from great code.

Pitfall #1: Using the Wrong Data Structure for Priority Queue

One of the most devastating mistakes in implementing Dijkstra's algorithm is using a naive list or array instead of a proper heap-based priority queue. This single decision can transform your algorithm from O((V + E) log V) to O(V²), making it fail on larger test cases.

⚠️ Common Mistake 1: Using a list with repeated sorting ⚠️

## ❌ INEFFICIENT: Using a list and sorting every iteration
def dijkstra_wrong(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    unvisited = [(0, start)]  # List of (distance, node)
    
    while unvisited:
        unvisited.sort()  # O(n log n) every iteration - DISASTER!
        current_dist, node = unvisited.pop(0)
        
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                unvisited.append((new_dist, neighbor))
    
    return dist

This code sorts the entire list on every iteration. If you have 1000 nodes, you're sorting potentially thousands of times. The performance degradation is catastrophic.

✅ Correct Implementation: Using heapq

import heapq

## ✅ EFFICIENT: Using a min-heap
def dijkstra_correct(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # Min-heap of (distance, node)
    
    while pq:
        current_dist, node = heapq.heappop(pq)  # O(log n) - much better!
        
        # Important: skip if we've found a better path already
        if current_dist > dist[node]:
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))  # O(log n)
    
    return dist

🎯 Key Principle: The choice of data structure directly impacts your algorithm's complexity class. Always use heapq in Python, PriorityQueue in Java, or priority_queue in C++ for Dijkstra's algorithm.

💡 Pro Tip: In Python, heapq only provides a min-heap. If you need a max-heap, negate the priorities: heappush(pq, (-priority, item)).

Pitfall #2: Forgetting to Track Visited Nodes

The second major pitfall is failing to properly handle visited nodes, which can cause infinite loops, Time Limit Exceeded (TLE) errors, or processing the same node multiple times unnecessarily.

There are actually two approaches to handling this, and understanding both is crucial:

Approach 1: Visited Set (for unweighted graphs or BFS)

from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([(start, 0)])  # (node, distance)
    visited = {start}  # Mark as visited when ADDED to queue
    
    while queue:
        node, dist = queue.popleft()
        
        if node == end:
            return dist
        
        for neighbor in graph[node]:
            if neighbor not in visited:  # Critical check!
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1  # No path found

Approach 2: Distance Checking (for Dijkstra's with weighted graphs)

For Dijkstra's algorithm, we typically don't use a visited set. Instead, we check if the current distance is stale:

def dijkstra_with_distance_check(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_dist, node = heapq.heappop(pq)
        
        # ✅ This prevents processing outdated entries
        if current_dist > dist[node]:
            continue  # We've already found a better path
        
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    
    return dist

⚠️ Warning: The if current_dist > dist[node]: continue check is absolutely critical. Without it, you'll process the same node multiple times with outdated distances, causing TLE on large graphs.

💡 Mental Model: Think of the heap as containing "rumors" about distances. When you pop a rumor, you need to verify it's still accurate before acting on it. If you've since learned a better distance, ignore the old rumor.

Pitfall #3: Incorrect Distance Array Initialization

A subtle but critical mistake is initializing distances incorrectly. This manifests in two common ways:

Mistake 3A: Using 0 for unvisited nodes

## ❌ WRONG: Initializing everything to 0
dist = {node: 0 for node in graph}
dist[start] = 0

❌ Wrong thinking: "I'll update distances as I go, so starting at 0 is fine."

✅ Correct thinking: "Unvisited nodes should have infinity as their distance because we haven't found any path to them yet. Only the start node should be 0."

Mistake 3B: Using a bounded value instead of infinity

## ⚠️ RISKY: Using a large number like 10^9
INF = 10**9
dist = {node: INF for node in graph}

While this might work for many test cases, it can fail if:

• The actual shortest path distance exceeds your chosen "infinity"
• Arithmetic operations cause overflow
• The graph has negative weights (in Bellman-Ford)

✅ Best Practice:

## ✅ CORRECT: Use float('inf') in Python
dist = {node: float('inf') for node in graph}
dist[start] = 0

## For array-based implementations:
dist = [float('inf')] * n
dist[start] = 0

🎯 Key Principle: float('inf') properly handles all comparison operations and clearly expresses intent. It's not just "a big number" – it's semantically correct.

Pitfall #4: Not Handling Edge Cases

Shortest path problems come with several tricky edge cases that can break your solution:

Edge Case 1: Disconnected Graphs

Not all nodes in a graph are necessarily reachable from your starting point.

Graph visualization:
    1 ---[5]--- 2      4 ---[3]--- 5
    |           |      (disconnected)
   [2]         [1]
    |           |
    3 ----------+

When returning results, you need to handle unreachable nodes:

def dijkstra_with_edge_cases(graph, start, end):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_dist, node = heapq.heappop(pq)
        
        if current_dist > dist[node]:
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    
    # ✅ Check if end is reachable
    if dist[end] == float('inf'):
        return -1  # No path exists
    return dist[end]

Edge Case 2: Self-Loops

A self-loop is an edge from a node to itself. In shortest path problems:

• Positive self-loops should be ignored (never optimal to use them)
• Negative self-loops indicate a negative cycle (undefined shortest path)

## Detecting self-loops in preprocessing
def preprocess_graph(edges):
    graph = {}
    for u, v, weight in edges:
        if u == v:  # Self-loop detected
            if weight < 0:
                return None  # Invalid graph - negative cycle
            continue  # Ignore positive self-loops
        
        if u not in graph:
            graph[u] = []
        graph[u].append((v, weight))
    
    return graph

Edge Case 3: Duplicate Edges (Multi-edges)

Your graph might have multiple edges between the same pair of nodes with different weights.

Node 1 ====[5]==== Node 2
       ====[3]====
       ====[7]====

For shortest path, you only need to keep the minimum weight edge:

def build_graph_from_edges(edges):
    graph = {}
    for u, v, weight in edges:
        if u not in graph:
            graph[u] = {}
        
        # Keep only the minimum weight edge between any pair
        if v in graph[u]:
            graph[u][v] = min(graph[u][v], weight)
        else:
            graph[u][v] = weight
    
    # Convert to list format for algorithm
    return {u: [(v, w) for v, w in neighbors.items()] 
            for u, neighbors in graph.items()}

Optimization Technique 1: Bidirectional Search

Bidirectional search is a powerful optimization that can dramatically reduce the search space when you're finding the shortest path between two specific nodes (as opposed to finding shortest paths from one source to all nodes).

💡 Mental Model: Instead of searching from start until you reach the end, search from both directions simultaneously. When the two search frontiers meet, you've found the shortest path.

Unidirectional search space:         Bidirectional search space:

     START                                START
      / \                                  / \
     /   \                                /   \
    /     \                              /     \
   /       \                            /       \
  /         \                       MEET HERE!
 /           \                         /   \
/_____________\                       /     \
      END                            /       \
                                   END

Area searched: πr²              Area searched: 2π(r/2)² = πr²/2

🎯 Key Principle: Bidirectional search reduces the search space from O(b^{d) to O(b}(d/2)), where b is the branching factor and d is the depth. This is exponentially better!

Implementation:

import heapq

def bidirectional_dijkstra(graph, start, end):
    # Forward search from start
    dist_forward = {node: float('inf') for node in graph}
    dist_forward[start] = 0
    pq_forward = [(0, start)]
    
    # Backward search from end (requires reverse graph)
    dist_backward = {node: float('inf') for node in graph}
    dist_backward[end] = 0
    pq_backward = [(0, end)]
    
    # Track best known path length
    best_path_length = float('inf')
    
    # Process both directions alternately
    while pq_forward and pq_backward:
        # Process forward direction
        if pq_forward:
            dist_f, node_f = heapq.heappop(pq_forward)
            
            # If this node was reached from backward search
            if dist_backward[node_f] != float('inf'):
                best_path_length = min(best_path_length, 
                                      dist_f + dist_backward[node_f])
            
            # Early termination: if current distance exceeds best path
            if dist_f > best_path_length:
                return best_path_length
            
            if dist_f <= dist_forward[node_f]:
                for neighbor, weight in graph[node_f]:
                    new_dist = dist_f + weight
                    if new_dist < dist_forward[neighbor]:
                        dist_forward[neighbor] = new_dist
                        heapq.heappush(pq_forward, (new_dist, neighbor))
        
        # Process backward direction (similar logic)
        if pq_backward:
            dist_b, node_b = heapq.heappop(pq_backward)
            
            if dist_forward[node_b] != float('inf'):
                best_path_length = min(best_path_length,
                                      dist_b + dist_forward[node_b])
            
            if dist_b > best_path_length:
                return best_path_length
            
            if dist_b <= dist_backward[node_b]:
                # Process backward edges (from neighbors to node_b)
                for neighbor in graph:
                    for next_node, weight in graph[neighbor]:
                        if next_node == node_b:
                            new_dist = dist_b + weight
                            if new_dist < dist_backward[neighbor]:
                                dist_backward[neighbor] = new_dist
                                heapq.heappush(pq_backward, (new_dist, neighbor))
    
    return best_path_length if best_path_length != float('inf') else -1

⚠️ Warning: Bidirectional search requires a reverse graph for the backward direction. For undirected graphs, this is simple (same graph). For directed graphs, you need to precompute the reverse edge relationships.

💡 Pro Tip: Bidirectional search is most effective when:

• You're finding a path between two specific nodes (not all-pairs shortest paths)
• The graph has high branching factor
• The shortest path is relatively long

It's less effective or even slower when:

• The graph is small or sparse
• The path is very short (overhead of maintaining two searches)
• You need paths from one source to all destinations (use regular Dijkstra's)

Optimization Technique 2: Early Termination

When you're only looking for the shortest path to a single destination (not all nodes), you can terminate as soon as you pop the destination from the priority queue:

def dijkstra_single_target(graph, start, target):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_dist, node = heapq.heappop(pq)
        
        # ✅ Early termination optimization
        if node == target:
            return current_dist  # Found shortest path to target!
        
        if current_dist > dist[node]:
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    
    return -1  # Target unreachable

🎯 Key Principle: Due to Dijkstra's greedy nature with a min-heap, the first time you pop a node from the heap, you've found its shortest distance. No need to continue after reaching your target.

Optimization Technique 3: Space Optimization for Path Reconstruction

Often you need not just the shortest distance, but the actual path. A naive approach stores all possible paths, which is memory-intensive.

❌ Inefficient approach:

## Don't store entire paths for each node
paths = {start: [start]}
for neighbor in graph[node]:
    paths[neighbor] = paths[node] + [neighbor]  # Creates many list copies!

✅ Efficient approach: Store only parent pointers and reconstruct the path at the end:

def dijkstra_with_path(graph, start, end):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    parent = {start: None}  # Only store parent pointers
    pq = [(0, start)]
    
    while pq:
        current_dist, node = heapq.heappop(pq)
        
        if node == end:
            break  # Early termination
        
        if current_dist > dist[node]:
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                parent[neighbor] = node  # Remember parent
                heapq.heappush(pq, (new_dist, neighbor))
    
    # Reconstruct path by following parent pointers backward
    if dist[end] == float('inf'):
        return -1, []  # No path
    
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = parent.get(current)
    path.reverse()
    
    return dist[end], path

This reduces space complexity from O(V²) (storing paths) to O(V) (storing parent pointers).

Performance Comparison and When to Use Each Technique

Let's consolidate everything we've learned into practical guidelines:

📋 Quick Reference Card: Pitfall Checklist

Aspect	❌ Wrong Approach	✅ Correct Approach
🔧 Priority Queue	List with sorting	heapq / heap
🔒 Visited Check	No check / wrong timing	Distance comparison
📊 Initialization	0 or arbitrary number	float('inf')
🎯 Edge Cases	Ignore disconnected nodes	Return -1 for unreachable
⚡ Termination	Process all nodes	Early exit at target
💾 Path Storage	Store full paths	Parent pointers

📋 Quick Reference Card: Optimization Decision Tree

Scenario	🎯 Best Approach	💡 Why
🔍 Single source to all	Standard Dijkstra	Need all distances
🎯 Single source to target	Dijkstra with early termination	Stop when target found
↔️ Large graph, specific target	Bidirectional search	Exponentially less search space
📝 Need actual path	Parent pointers	Memory efficient
⚖️ Negative weights	Bellman-Ford	Dijkstra fails
🌐 Dense graph (many edges)	Matrix representation	Better cache locality
🕸️ Sparse graph (few edges)	Adjacency list	Less memory

Real-World Performance Impact

🤔 Did you know? On a graph with 10,000 nodes and average degree of 10:

• Using a list instead of heap: ~100x slower
• Missing the visited check: May not terminate at all (TLE)
• Using bidirectional search: ~100x faster for point-to-point queries
• Proper early termination: ~10-50x faster when target is close

These aren't small optimizations – they're the difference between passing and failing LeetCode's time constraints.

Debugging Checklist for Shortest Path Problems

When your solution isn't working, check these in order:

🔧 Debug Checklist:

1. Data structure: Are you using heapq or equivalent?
2. Initialization: Is start node at 0, others at infinity?
3. Visited logic: Are you checking current_dist > dist[node]?
4. Edge weights: Are they being added correctly?
5. Edge cases: Handle disconnected components?
6. Return value: Returning -1 for no path?
7. Graph construction: Any duplicate edges or self-loops?
8. Heap elements: Are you pushing (distance, node) not (node, distance)?

💡 Pro Tip: Add logging to see what your algorithm is doing:

while pq:
    current_dist, node = heapq.heappop(pq)
    print(f"Processing node {node} with distance {current_dist}")
    # ... rest of algorithm

This simple debug output can reveal if you're processing nodes in the wrong order or with wrong distances.

Summary: Best Practices

Mastering shortest path algorithms isn't just about understanding the theory – it's about avoiding the subtle implementation mistakes that cause solutions to fail and applying optimizations that make them blazingly fast.

🧠 Key Takeaways:

• Always use a proper heap-based priority queue
• Check if current_dist > dist[node] to skip outdated entries
• Initialize distances to float('inf') except source (0)
• Handle edge cases: disconnected graphs, self-loops, multi-edges
• Use bidirectional search for large graphs with specific targets
• Implement early termination when searching for a single destination
• Store parent pointers instead of full paths for memory efficiency

By internalizing these patterns and pitfalls, you'll write shortest path solutions that are not only correct but also optimized for competitive programming time constraints. The difference between a naive implementation and an optimized one can be orders of magnitude in performance – and on LeetCode, that often means the difference between Accepted and Time Limit Exceeded.

Summary and Quick Reference Guide

Congratulations! You've now mastered the fundamental shortest path algorithms that power countless real-world applications and LeetCode problems. Before this lesson, you may have struggled to choose between different approaches or fumbled through implementations with subtle bugs. Now you possess a structured framework for algorithm selection, implementation best practices, and the confidence to tackle any shortest path problem efficiently.

What You've Learned

You started with Dijkstra's algorithm, understanding its greedy approach with priority queues for non-negative weighted graphs. You then explored Bellman-Ford, which sacrifices some speed for the ability to handle negative weights and detect negative cycles. You've seen BFS for unweighted graphs and understood when a simple queue beats more complex approaches. Finally, you learned practical implementation patterns, common pitfalls, and optimization techniques that separate working code from elegant, efficient solutions.

Algorithm Selection Decision Tree

Choosing the right algorithm is crucial for both correctness and efficiency. Follow this decision flowchart:

                    START: Shortest Path Problem
                                |
                                v
                    Are all edges unweighted?
                        /              \
                      YES               NO
                       |                 |
                       v                 v
                   Use BFS       Does graph have negative
                (O(V+E), simple)    edge weights?
                                    /            \
                                  YES             NO
                                   |               |
                                   v               v
                          Need to detect      Single source or
                          negative cycles?    multiple queries?
                            /        \              /         \
                          YES        NO        SINGLE      MULTIPLE
                           |          |            |            |
                           v          v            v            v
                      Bellman-Ford  Bellman-Ford  Dijkstra   Floyd-Warshall
                      O(V*E)        O(V*E)       O((V+E)logV) O(V³)
                      Returns       Works with                Or run Dijkstra
                      detection     negative                  V times
                                   weights

🎯 Key Principle: Always check for negative weights first. Using Dijkstra's algorithm with negative weights produces incorrect results, not just slower ones.

💡 Pro Tip: For competitive programming, if you see "weighted graph" without mention of negative weights, it's usually safe to assume non-negative weights and use Dijkstra. However, always verify in production code.

Quick Reference: Algorithm Comparison

📋 Quick Reference Card: Shortest Path Algorithms

Algorithm	Time Complexity	Space Complexity	Edge Weights	Detects Negative Cycles	Best Use Case
🚀 BFS	O(V + E)	O(V)	Unweighted only	❌ No	Simple, unweighted graphs; maze problems
⭐ Dijkstra	O((V+E) log V) with heap	O(V)	Non-negative	❌ No	Most common; road networks, weighted grids
💪 Bellman-Ford	O(V × E)	O(V)	Any (including negative)	✅ Yes	Currency arbitrage, graphs with negative weights
🌐 Floyd-Warshall	O(V³)	O(V²)	Any (including negative)	✅ Yes	All-pairs shortest paths, small dense graphs
🎯 A*	O(E) with good heuristic	O(V)	Non-negative	❌ No	Pathfinding with goal; game AI, GPS navigation

Detailed Algorithm Properties

BFS (Breadth-First Search)

• 🔧 Implementation: Simple queue, no priority needed
• 🎯 Optimal for: Unweighted graphs, minimum number of edges
• ⚠️ Limitation: Cannot handle weighted edges at all
• 📚 LeetCode patterns: Word Ladder, Shortest Path in Binary Matrix

Dijkstra's Algorithm

• 🔧 Implementation: Min-heap/priority queue required
• 🎯 Optimal for: Single-source, non-negative weights, ~80% of problems
• ⚠️ Limitation: Fails silently with negative weights (gives wrong answer)
• 📚 LeetCode patterns: Network Delay Time, Path with Minimum Effort

Bellman-Ford Algorithm

• 🔧 Implementation: Simple nested loops, no complex data structures
• 🎯 Optimal for: Negative weights, distributed computing
• ⚠️ Limitation: Much slower than Dijkstra on large graphs
• 📚 LeetCode patterns: Cheapest Flights Within K Stops, Network Delay with constraints

Floyd-Warshall Algorithm

• 🔧 Implementation: Triple nested loop, simple but memory-intensive
• 🎯 Optimal for: All-pairs shortest paths, dense graphs with V < 400
• ⚠️ Limitation: Cubic time makes it impractical for large graphs
• 📚 LeetCode patterns: Find the City With Smallest Number of Neighbors

🤔 Did you know? Dijkstra's algorithm was conceived by Edsger Dijkstra in 1956 while sitting in a café in Amsterdam, and he designed it without pen and paper to prove it was elegant enough to understand mentally!

Implementation Checklist

Use this checklist before submitting your solution to avoid the most common bugs:

Pre-Implementation Phase

✅ Graph Analysis

• Identify if graph is weighted or unweighted
• Check for negative edge weights
• Determine if graph is directed or undirected
• Estimate graph size (V and E) for complexity analysis
• Identify if single-source or all-pairs problem

✅ Algorithm Selection

• Selected algorithm matches graph properties
• Time complexity acceptable for input constraints
• Space complexity fits memory limits

Dijkstra's Algorithm Checklist

import heapq
from collections import defaultdict

def dijkstra_template(graph, start, n):
    """
    ✅ Template for Dijkstra's Algorithm
    graph: adjacency list {node: [(neighbor, weight), ...]}
    start: starting node
    n: number of nodes
    """
    # ✅ Initialize distances to infinity
    dist = [float('inf')] * n
    dist[start] = 0
    
    # ✅ Min-heap: (distance, node)
    # CRITICAL: distance comes first for proper ordering
    heap = [(0, start)]
    
    # ✅ Optional: visited set to avoid reprocessing
    visited = set()
    
    while heap:
        curr_dist, node = heapq.heappop(heap)
        
        # ⚠️ CRITICAL: Skip if already visited
        if node in visited:
            continue
        visited.add(node)
        
        # ⚠️ CRITICAL: Skip if this is an outdated entry
        if curr_dist > dist[node]:
            continue
        
        # Process neighbors
        for neighbor, weight in graph[node]:
            new_dist = curr_dist + weight
            
            # ✅ Only update if found shorter path
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return dist

Dijkstra Implementation Checklist:

• Distance array initialized to infinity (except source = 0)
• Heap entries are (distance, node) with distance first
• Check if node already visited before processing
• Validate curr_dist <= dist[node] to skip outdated entries
• Only push to heap when distance improves
• Handle unreachable nodes (distance remains infinity)

⚠️ Common Mistake 1: Pushing (node, distance) instead of (distance, node) to the heap. This breaks the min-heap property! ⚠️

⚠️ Common Mistake 2: Forgetting to check if a node is already visited, leading to redundant processing and TLE (Time Limit Exceeded). ⚠️

Bellman-Ford Algorithm Checklist

def bellman_ford_template(edges, n, start):
    """
    ✅ Template for Bellman-Ford Algorithm
    edges: list of (u, v, weight) tuples
    n: number of nodes
    start: starting node
    Returns: (distances, has_negative_cycle)
    """
    # ✅ Initialize distances
    dist = [float('inf')] * n
    dist[start] = 0
    
    # ✅ Relax all edges V-1 times
    for i in range(n - 1):
        updated = False
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                updated = True
        
        # ✅ Optimization: early termination if no updates
        if not updated:
            break
    
    # ✅ Check for negative cycles (Vth iteration)
    has_negative_cycle = False
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            has_negative_cycle = True
            break
    
    return dist, has_negative_cycle

Bellman-Ford Implementation Checklist:

• Relax edges exactly V-1 times (not V or V-2)
• Check source reachability: dist[u] != infinity before relaxing
• Implement early termination optimization when no updates occur
• Perform one extra iteration to detect negative cycles
• Handle the case where negative cycle exists (return appropriately)

⚠️ Common Mistake 3: Running the loop V times instead of V-1 times. This can give false positive for negative cycle detection! ⚠️

BFS for Unweighted Graphs Checklist

from collections import deque

def bfs_shortest_path(graph, start, n):
    """
    ✅ Template for BFS on unweighted graph
    graph: adjacency list {node: [neighbors]}
    start: starting node
    n: number of nodes
    """
    # ✅ Distance array doubles as visited tracker
    dist = [-1] * n  # -1 means unvisited
    dist[start] = 0
    
    # ✅ Simple queue (not priority queue)
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        for neighbor in graph[node]:
            # ✅ Only visit unvisited nodes
            if dist[neighbor] == -1:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    
    return dist

BFS Implementation Checklist:

• Use simple queue (collections.deque), not priority queue
• Mark nodes as visited when added to queue (not when popped)
• Distance increments by 1 for each level
• No need for distance comparison (first visit is shortest)

💡 Remember: In BFS, the first time you reach a node is always the shortest path. No need to update distances!

Advanced Topics and Extensions

Once you've mastered the core algorithms, these advanced topics will expand your problem-solving toolkit:

A* Search Algorithm

A (A-Star)* is an informed search algorithm that extends Dijkstra's algorithm with a heuristic function to guide the search toward the goal more efficiently.

Key Concept: Instead of exploring nodes in order of distance from source, A* uses f(n) = g(n) + h(n) where:

• g(n) = actual distance from start to node n
• h(n) = heuristic estimate from node n to goal
• f(n) = estimated total distance through node n

import heapq

def a_star(graph, start, goal, heuristic):
    """
    A* pathfinding algorithm
    heuristic: function that estimates distance to goal
    """
    # Priority queue: (f_score, g_score, node)
    heap = [(0 + heuristic(start, goal), 0, start)]
    g_score = {start: 0}
    visited = set()
    
    while heap:
        f, g, node = heapq.heappop(heap)
        
        if node == goal:
            return g  # Found shortest path!
        
        if node in visited:
            continue
        visited.add(node)
        
        for neighbor, weight in graph[node]:
            new_g = g + weight
            
            if neighbor not in g_score or new_g < g_score[neighbor]:
                g_score[neighbor] = new_g
                f_score = new_g + heuristic(neighbor, goal)
                heapq.heappush(heap, (f_score, new_g, neighbor))
    
    return float('inf')  # No path found

Common Heuristics:

• 🎯 Manhattan Distance: |x1-x2| + |y1-y2| (grid with 4-directional movement)
• 🎯 Euclidean Distance: sqrt((x1-x2)² + (y1-y2)²) (grid with diagonal movement)
• 🎯 Chebyshev Distance: max(|x1-x2|, |y1-y2|) (grid with 8-directional movement)

⚠️ Critical Property: The heuristic must be admissible (never overestimates) and consistent for A* to guarantee optimal solution.

💡 Real-World Example: Google Maps uses variations of A* for routing. The heuristic estimates remaining distance, allowing the algorithm to explore promising routes first rather than expanding uniformly in all directions.

Johnson's Algorithm for All-Pairs Shortest Path

Johnson's Algorithm efficiently computes all-pairs shortest paths even with negative weights by combining Bellman-Ford and Dijkstra:

1. Add a new node connected to all other nodes with weight 0
2. Run Bellman-Ford from this new node to get reweighting function h(v)
3. Reweight all edges: w'(u,v) = w(u,v) + h(u) - h(v)
4. Run Dijkstra from each node on reweighted graph
5. Convert distances back: dist(u,v) = dist'(u,v) - h(u) + h(v)

Time Complexity: O(V² log V + VE) - better than Floyd-Warshall for sparse graphs!

🎯 Key Principle: Reweighting preserves shortest paths while making all edges non-negative, allowing us to use the faster Dijkstra algorithm.

Bidirectional Search

Run two simultaneous searches: one from source forward, one from goal backward. Stop when they meet. This can reduce the search space from O(b^{d) to O(b}(d/2)).

Use Case: When you know both source and destination (e.g., point-to-point routing).

Practice Problems by Difficulty

Here's a curated progression of LeetCode problems to solidify your understanding:

Easy Level (Foundation Building)

1. [LeetCode 1971] Path Exists in Graph - Basic BFS/DFS
2. [LeetCode 997] Find the Town Judge - Graph basics
3. [LeetCode 1779] Find Nearest Point with Same Coordinates - Distance concepts

Medium Level (Core Practice)

4. [LeetCode 743] Network Delay Time ⭐ - Classic Dijkstra, single-source

   • 💡 Perfect introduction to Dijkstra's algorithm
   • Practice: priority queue implementation

5. [LeetCode 787] Cheapest Flights Within K Stops ⭐ - Bellman-Ford variant

   • 💡 Introduces constraint-based shortest path (limited edges)
   • Practice: modified Bellman-Ford with edge limit

6. [LeetCode 1091] Shortest Path in Binary Matrix - BFS on grid

   • 💡 Grid problems are disguised graph problems
   • Practice: converting 2D grid to graph

7. [LeetCode 1631] Path with Minimum Effort ⭐ - Modified Dijkstra

   • 💡 Redefine "distance" as maximum effort along path
   • Practice: adapting Dijkstra for different metrics

8. [LeetCode 1334] Find the City With Smallest Number of Neighbors - Floyd-Warshall

   • 💡 Classic all-pairs shortest path problem
   • Practice: Floyd-Warshall implementation

9. [LeetCode 1514] Path with Maximum Probability - Modified Dijkstra

   • 💡 Use max-heap instead of min-heap, multiply probabilities
   • Practice: inverting the optimization direction

Hard Level (Advanced Mastery)

10. [LeetCode 778] Swim in Rising Water - Binary search + BFS/Dijkstra

    • 💡 Combines multiple concepts; can solve with Dijkstra or binary search
    • Practice: identifying when shortest path applies

11. [LeetCode 882] Reachable Nodes in Subdivided Graph - Advanced Dijkstra

    • 💡 Tricky problem involving subdivided edges
    • Practice: handling complex graph transformations

12. [LeetCode 864] Shortest Path to Get All Keys - BFS with state

    • 💡 State-space search: (position, keys_collected)
    • Practice: expanding state beyond just position

13. [LeetCode 1368] Minimum Cost to Make at Least One Valid Path - 0-1 BFS

    • 💡 Special case: edges have weight 0 or 1
    • Practice: optimized BFS with deque (add to front for 0-weight)

Practice Strategy

🧠 Mnemonic for Problem Approach: "GNAW"

• Graph properties (weighted? negative? directed?)
• Number of sources (single vs. all-pairs)
• Algorithm selection (decision tree)
• Write and test (implement with checklist)

💡 Pro Tip: Solve problems in groups of similar types. Do 3-4 Dijkstra problems in a row to build muscle memory, then move to Bellman-Ford problems. This spaced repetition solidifies patterns.

Final Critical Reminders

⚠️ Critical Point 1: Dijkstra with negative weights gives WRONG answers, not just slow answers. Always check edge weights first.

⚠️ Critical Point 2: In a min-heap for Dijkstra, the tuple must be (distance, node) with distance first. Reversing this is a silent bug that's hard to debug.

⚠️ Critical Point 3: Always handle the case where the destination is unreachable. Check if dist[target] == infinity before returning.

⚠️ Critical Point 4: For grid problems, validate coordinates before accessing the grid: 0 <= x < rows and 0 <= y < cols.

Practical Applications and Next Steps

Now that you've mastered shortest path algorithms, you can confidently tackle:

Practical Applications

1. Navigation Systems 🗺️

   • GPS routing uses A* with road network graphs
   • Real-time traffic updates = dynamic edge weight changes
   • Alternative routes = k-shortest paths problem

2. Network Routing 🌐

   • Internet packet routing uses variants of Dijkstra
   • Bellman-Ford powers BGP (Border Gateway Protocol)
   • Negative weights represent routing policies

3. Game Development 🎮

   • AI pathfinding for NPCs uses A*
   • Minimax with shortest path for strategic planning
   • Dynamic obstacle avoidance = real-time graph updates

Next Steps for Mastery

1. Practice Consistently 📚

   • Solve 2-3 problems per week for next month
   • Review your solutions after 1 week and 1 month
   • Time yourself to build speed for interviews

2. Explore Variations 🔧

   • K-shortest paths algorithm
   • Shortest path with forbidden paths
   • Time-dependent shortest paths
   • Stochastic shortest path problems

3. Study Advanced Topics 🎓

   • Contraction Hierarchies (used in production routing)
   • Highway Hierarchies
   • Transit Node Routing
   • Bidirectional A* with landmarks

💡 Real-World Example: When you use Uber or Lyft, the app runs a shortest path algorithm considering: distance, estimated time (varying by traffic), tolls, and road restrictions. This multi-objective shortest path problem uses weighted combinations of Dijkstra's algorithm running on preprocessed road networks with billions of edges!

Conclusion

You now possess a complete mental framework for shortest path problems. You can quickly identify graph properties, select the optimal algorithm, implement it correctly using proven templates, and avoid common pitfalls. Whether you're solving LeetCode problems, preparing for technical interviews, or building production systems, these algorithms form an essential part of your computer science foundation.

The key to mastery is deliberate practice. Use the decision tree, reference tables, and implementation checklists until they become second nature. Before long, you'll recognize shortest path patterns instantly and implement solutions confidently and correctly on your first attempt.

Happy coding, and may your paths always be shortest! 🚀