Dijkstra’s Algorithm

Scope — Single-source shortest path with non-negative weights, via a priority queue. See also: Dijkstra_examples.md — the eleven worked problems behind these templates; shortest_path_comparison.md — which algorithm to reach for; Bellman-Ford.md — when weights can be negative; Floyd-Warshall.md — when you need all pairs; heap.md — the priority queue underneath.

LeetCode Problem Lists

• Shortest Path
• Graph Theory
• Heap (Priority Queue)

Overview

Dijkstra’s algorithm is a greedy algorithm that solves the single-source shortest path problem for a graph with NON-NEGATIVE edge weights. It finds the shortest path from a starting node (source) to all other nodes in the graph.

Key Properties

• Time Complexity: O((V + E) log V) with binary heap, O(V²) with array
• Space Complexity: O(V) for distance array and visited set
• Core Idea: Greedily select the unvisited node with minimum distance
• When to Use: Single-source shortest path with non-negative weights
• Limitation: Cannot handle negative edge weights, maximise a sum of gains (a longest path), or a path where the cells already used decide where it can go next (LC 1219) — see When Dijkstra does not apply

Core Characteristics

• Greedy Algorithm: Always selects the minimum distance node
• Priority Queue: Uses min-heap for efficient minimum extraction
• Relaxation: Updates distances when shorter paths are found
• Finalization: Once visited, a node’s distance is optimal

References

• Dijkstra’s Algorithm Visualization
• CP Algorithms - Dijkstra
• Bellman-Ford Cheatsheet - For negative weight handling comparison
• Floyd-Warshall Cheatsheet - For all-pairs shortest path comparison

Problem Categories

Category 1: Classic Shortest Path

• Description: Standard single-source shortest path problems
• Examples: LC 743 (Network Delay), LC 1514 (Path with Max Probability)
• Pattern: Direct application of Dijkstra’s algorithm

Category 2: Shortest Path with Constraints ⚠️ Dijkstra VARIANT

• Description: Shortest path with an extra constraint dimension (stops, obstacles, keys, time)
• Examples: LC 787 (Cheapest Flights K Stops), LC 1293 (Shortest Path K Obstacle Removal), LC 864 (Get All Keys), LC 1928 (Minimum Cost K Waypoints)
• Pattern: 2D-state Dijkstra — state is (cost, node, constraint) instead of (cost, node)
• Why it’s a variant: Same node at different constraint values = different states. Standard visited[node] or dist[node] pruning is WRONG here — it would discard valid paths that reach the same node with a different remaining budget.
• Pruning rule: best[(node, constraint)] <= cost (2D best-map, not 1D dist array)

Category 3: Grid-based Shortest Path

• Description: Finding optimal paths in 2D grids
• Examples: LC 64 (Minimum Path Sum), LC 1631 (Path Min Effort), LC 778 (Swim in Rising Water)
• Pattern: Dijkstra on implicit graph (grid cells as nodes)
• ⚠️ Special Note: LC 64 can use pure DP instead of Dijkstra (see below)

Category 4: Multi-Source Shortest Path

• Description: Multiple starting points to find shortest paths
• Examples: LC 2812 (Find Safest Path), LC 1162 (As Far from Land)
• Pattern: Initialize multiple sources or use super source

Category 5: Time-Dependent Shortest Path

• Description: Path costs change based on time or sequence
• Examples: LC 2045 (Second Minimum Time), LC 882 (Reachable Nodes)
• Pattern: Track time/state in priority queue

Choosing Dijkstra: the two questions

Nine of this sheet’s sections used to argue about LC 1631 in one form or another. They reduce to two questions you can ask of any shortest-path problem, plus one alternative framing worth knowing.

1) Is the cost additive, and can you order the cells? — LC 64 vs LC 1631 ★★★★☆Priority 4 of 5 — High value — a gap here costs you rounds

Question: Do we really need dist[r][c] (tracking minimum cost to reach each cell) for Dijkstra? Or is pure DP enough?

Answer: It depends on movement directions:

LC 64: Minimum Path Sum ✅ Pure DP is Sufficient

Movement: RIGHT only ↓ or DOWN only →

• Why DP works: You can only reach cell (i,j) from (i-1,j) or (i,j-1)
• No need for dist[][]: Each cell is computed exactly once in topological order
• No revisits: You can never find a “better path” after already computing a cell
• Solution: Simple 2D DP or O(min(m,n)) space 1D DP

// Pure DP - NO dist[][] needed
public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];
    
    // First column: only from above
    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];
    
    // First row: only from left
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];
    
    // Fill rest
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
    
    return dp[m-1][n-1];
}
// Time: O(m*n), Space: O(min(m,n))

LC 1631: Path With Minimum Effort ⚠️ Dijkstra + dist[][] Needed

Movement: UP, DOWN, LEFT, RIGHT (all 4 directions)

• Why Dijkstra needed: You might reach a cell from multiple paths, and later find a better path
• dist[][] is essential: Tracks “best cost found so far” for each cell
• Revisits possible: When moving in all 4 directions, you can revisit cells with better costs
• Solution: Dijkstra with dist[][] + PriorityQueue

// Dijkstra + dist[][] - NECESSARY for 4-directional movement
public int minimumEffortPath(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    
    // dist[r][c] = minimum effort found so far to reach (r,c)
    int[][] dist = new int[m][n];
    for (int[] row : dist)
        Arrays.fill(row, Integer.MAX_VALUE);
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
    pq.offer(new int[]{0, 0, 0});
    dist[0][0] = 0;
    
    int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int r = cur[0], c = cur[1], cost = cur[2];
        
        // Already processed with better cost
        if (cost > dist[r][c]) continue;
        
        if (r == m-1 && c == n-1) return cost;
        
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                int newCost = Math.max(cost, Math.abs(heights[nr][nc] - heights[r][c]));
                if (newCost < dist[nr][nc]) {
                    dist[nr][nc] = newCost;
                    pq.offer(new int[]{nr, nc, newCost});
                }
            }
        }
    }
    return -1;
}
// Time: O(m*n*log(m*n)), Space: O(m*n)

Summary Table — LC 64 vs LC 1631

Two consequences worth stating explicitly, because they are the two ways this goes wrong:

Why DP cannot rescue LC 1631. A: Because of movement direction:

• LC 64: Only move RIGHT/DOWN → Topological order exists → DP works ✅
• LC 1631: Can move UP/DOWN/LEFT/RIGHT → Cycles exist → DP fails ❌

With 4-directional movement, you can have circular dependencies:

(1,1) → (1,2) → (2,2) → (2,1) → (1,1)

DP requires dependencies to form a DAG (no cycles), so Dijkstra or Binary Search required.

Why “cost” and “effort” are not the same quantity. A: They measure different things in different problems:

• Cost (LC 64, 1263): Sum of all values along path = cost += value
• Effort (LC 1631): Max difference between consecutive cells = effort = max(effort, |diff|)

Cost is additive; effort is not. This non-additivity is why DP fails.

2) Do you need dist[], or is visited[] enough? ★★★★☆Priority 4 of 5 — High value — a gap here costs you rounds

dist[r][c] = "What's the MINIMUM cost I've found SO FAR to reach (r,c)?"

• Initialize: dist[r][c] = Integer.MAX_VALUE (unknown)
• Update: When PQ pops a cell with cost C, check if (C > dist[r][c]) continue;
  • If true, we already found a better path → skip processing
  • This automatically prevents reprocessing without explicit visited array
• Essential when: Multiple paths can reach the same cell → Dijkstra refinement needed

A: No, you use ONE or the OTHER:

• Option A: dist[][] → Check if (newCost < dist[r][c]) before processing
• Option B: visited[] → Mark as visited after first pop from PQ

Both prevent reprocessing the same cell. Pick whichever feels clearer — but they are not always interchangeable. See below for when best[]/dist[] is actually required vs. when you can simplify to comparing the next candidate path directly against the current (just-popped) path.

There are two different comparisons a Dijkstra implementation can make when it looks at a candidate edge cur_node -> nxt_node:

Key concept in one line:

best[] answers “is this candidate better than anything I’ve seen before for this state?” — needed whenever a state can be legitimately revisited with a different value. visited[]-only answers “has this state already been finalized?” — sufficient only when the heap’s pop-order guarantee (first pop = optimal) fully covers the state, i.e. no extra constraint dimension.

Classic Dijkstra problems by type:

Rule of thumb: if you can answer “is node alone a complete description of where you are in the search?” with yes, visited[]-only is safe. The moment the answer becomes “no — I also need to know how many stops/keys/obstacles I’ve used,” you must upgrade to a best[]/dist[] map keyed by (node, constraint).

A: Yes! The check if (cost > dist[r][c]) continue; IS your visited mechanism:

• First time we pop (r,c): cost == dist[r][c] → process
• Later pops to (r,c): cost > dist[r][c] → skip (it’s like “already visited”)

So you get the benefit of visited[] semantics without an extra array.

3) When Union Find is the better framing

A: Use Union Find when:

• You’re comfortable building explicit edge list
• You want to see the problem as a graph connectivity problem
• You’re practicing Kruskal’s algorithm

Both have same time complexity O(m×n×log(m×n)), but Dijkstra is usually more intuitive for grid problems.

Templates & Algorithms

Template Comparison Table

Universal Dijkstra Template ★★★★★Priority 5 of 5 — Must know — expect it in almost every loop

import heapq
import collections

def dijkstra(n, edges, src, dst):
    # Build adjacency list
    graph = collections.defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
    
    # Min heap: (distance, node)
    pq = [(0, src)]
    # Distance array
    dist = [float('inf')] * n
    dist[src] = 0
    # Visited set (optional but recommended)
    visited = set()
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # Skip if already processed with better distance
        if u in visited:
            continue
        visited.add(u)
        
        # Found destination
        if u == dst:
            return d
        
        # Relax edges
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    return dist[dst] if dist[dst] != float('inf') else -1

Core Steps — the loop in seven moves (LC 743)

The same loop, read off LC 743 Network Delay Time, where the source is the given node k:

1. Start from the source k with distance 0.
2. Push (0, k) into the min-heap.
3. Pop the node whose accumulated distance is smallest.
4. Explore every neighbor of that node.
5. Compute each neighbor’s new distance: cur_dist + edge_cost.
6. Push every neighbor whose shortest distance is not yet finalized.
7. Repeat until the min-heap is empty.

Why the first pop is final: every heap entry carries the full path cost from k, and the heap always yields the smallest one next — with no negative edges, nothing popped later can undercut it. So the first pop of a node finalizes it, and any later pop of the same node is a stale entry to skip.

Pitfall: this is not level-order BFS. Pop one node per iteration; a for _ in range(len(q)) level loop processes nodes in hop order, not cost order, and breaks the guarantee above.

# LC 743 - Network Delay Time
# IDEA: Dijkstra (min-heap PQ + BFS); stop as soon as all n nodes are finalized
# time = O((V + E) log V), space = O(V + E)
import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))          # u -> (neighbor, travel time)

    min_heap = [(0, k)]                  # steps 1-2: (accumulated time, node)
    visited = set()                      # nodes whose shortest time is finalized

    while min_heap:                      # step 7
        time, node = heapq.heappop(min_heap)   # step 3
        if node in visited:              # stale entry: already finalized cheaper
            continue
        visited.add(node)
        if len(visited) == n:            # last node reached = network delay
            return time
        for neighbor, weight in graph[node]:   # step 4
            if neighbor not in visited:  # step 6
                heapq.heappush(min_heap, (time + weight, neighbor))  # step 5
    return -1                            # heap emptied, some node unreachable

Template 1: Basic Dijkstra

def dijkstra_basic(n, edges, src):
    """Find shortest paths from src to all nodes"""
    graph = collections.defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
    
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]  # (distance, node)
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:  # Already processed
            continue
        
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    return dist

Template 2: Dijkstra with Constraints (2D-State Variant) ★★★★☆Priority 4 of 5 — High value — a gap here costs you rounds

Core idea — why this is NOT standard Dijkstra:

Why visited[node] / dist[node] breaks:

Example: src=0, dst=3, K=2
  Path A: 0→1→3  cost=900  stops=1  ← fewer stops but more expensive
  Path B: 0→1→2→3  cost=210  stops=2  ← more stops but cheaper

Standard dist[1] would be finalized at first pop (cost=100).
Path B would try to re-expand node 1 at stops=1, but dist[1] check blocks it.
→ Wrong: path B never explored, answer is incorrect.

With best[(node, stops)]: (node=1, stops=0) and (node=1, stops=1) are DIFFERENT states.
Both get explored independently. Correct answer found.

def dijkstra_constrained(n, edges, src, dst, k):
    graph = collections.defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))

    # (cost, node, stops_used)
    pq = [(0, src, 0)]

    # KEY: 2D best-map — best[(node, stops)] = min cost to reach node using exactly 'stops' edges
    # This replaces the 1D dist[] array used in standard Dijkstra
    best = {}

    while pq:
        cost, u, stops = heapq.heappop(pq)

        # First pop of (u, dst) is optimal (min-heap guarantee for this state)
        if u == dst:
            return cost

        # Constraint exceeded — prune this branch
        if stops > k:
            continue

        # 2D pruning: skip if we've already reached (node, stops) cheaper
        if (u, stops) in best and best[(u, stops)] <= cost:
            continue
        best[(u, stops)] = cost

        for v, w in graph[u]:
            heapq.heappush(pq, (cost + w, v, stops + 1))

    return -1

General constrained Dijkstra skeleton:

# Replace 'stops' with whatever constraint your problem has:
# - stops remaining (LC 787)
# - obstacles budget (LC 1293)
# - keys bitmask (LC 864)
# - discount count (LC 2093)

pq = [(0, src, initial_constraint)]
best = {}   # best[(node, constraint)] = min cost

while pq:
    cost, node, constraint = heapq.heappop(pq)
    if node == dst: return cost
    if constraint is exhausted: continue
    if (node, constraint) in best and best[(node, constraint)] <= cost: continue
    best[(node, constraint)] = cost
    for nei, w in graph[node]:
        heapq.heappush(pq, (cost + w, nei, updated_constraint))

Similar Problems (same 2D-state pattern):

Template 3: Grid-based Dijkstra ★★★★☆Priority 4 of 5 — High value — a gap here costs you rounds

def dijkstra_grid(grid):
    """Find minimum cost path in 2D grid"""
    rows, cols = len(grid), len(grid[0])
    
    # Min heap: (cost, row, col)
    pq = [(0, 0, 0)]
    # Distance matrix
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while pq:
        cost, r, c = heapq.heappop(pq)
        
        if r == rows - 1 and c == cols - 1:
            return cost
        
        if cost > dist[r][c]:
            continue
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                # Calculate new cost (problem-specific)
                new_cost = max(cost, abs(grid[nr][nc] - grid[r][c]))
                
                if new_cost < dist[nr][nc]:
                    dist[nr][nc] = new_cost
                    heapq.heappush(pq, (new_cost, nr, nc))
    
    return -1

Template 4: Multi-Source Dijkstra ★★★☆☆Priority 3 of 5 — Worth knowing — usually a variant of a must-know pattern

def dijkstra_multi_source(n, edges, sources):
    """Shortest paths from multiple sources"""
    graph = collections.defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
    
    dist = [float('inf')] * n
    pq = []
    
    # Initialize all sources
    for src in sources:
        dist[src] = 0
        heapq.heappush(pq, (0, src))
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    return dist

Template 5: Bidirectional Dijkstra

def dijkstra_bidirectional(n, edges, src, dst):
    """Optimize by searching from both ends"""
    graph = collections.defaultdict(list)
    reverse = collections.defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        reverse[v].append((u, w))
    
    def dijkstra_helper(start, adj, other_dist):
        dist = [float('inf')] * n
        dist[start] = 0
        pq = [(0, start)]
        visited = set()
        min_path = float('inf')
        
        while pq:
            d, u = heapq.heappop(pq)
            if u in visited:
                continue
            visited.add(u)
            
            # Check if we can form a complete path
            if other_dist[u] != float('inf'):
                min_path = min(min_path, d + other_dist[u])
            
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(pq, (dist[v], v))
        
        return dist, min_path
    
    # Run both directions
    dist_fwd, path1 = dijkstra_helper(src, graph, [float('inf')] * n)
    dist_bwd, path2 = dijkstra_helper(dst, reverse, dist_fwd)
    
    return min(path1, path2, dist_fwd[dst])

Problems by Pattern

Classic Shortest Path Problems

Constrained Path Problems

Grid-based Problems

Multi-Source Problems

Time/State Dependent Problems

Worked Examples

Eleven problems live in Dijkstra_examples.md, grouped by what the state looks like — which is the thing that decides the implementation:

Decision Framework

Pattern Selection Strategy

Dijkstra Algorithm Selection Flowchart:

1. What does the path's value do as the path grows?
   ├── MINIMISE a cost that can only grow   → Continue to 2
   ├── MAXIMISE a value that can only shrink AND keeps two arrivals
   │   in the same order (× p with 0 ≤ p ≤ 1, the smallest cell so far)
   │   → max-heap Dijkstra (LC 1514, 1102); with a K-edge / stop limit,
   │     key the state on (node, edges_used) as in step 5 — a likelier
   │     arrival with no edges left must not block a viable one
   └── MAXIMISE a value that keeps growing (a sum of gold / score)
       → not Dijkstra: backtracking (LC 1219), or DP on a DAG —
         see "When Dijkstra does not apply"

2. Are all edge weights non-negative?
   ├── NO → Use Bellman-Ford or SPFA
   └── YES → Continue to 3

3. Single source or multiple sources?
   ├── Multiple → Use Multi-Source Dijkstra (Template 4)
   └── Single → Continue to 4

4. Is it on a graph or grid?
   ├── Grid → Use Grid-based Dijkstra (Template 3)
   └── Graph → Continue to 5

5. Any constraints (K stops, budget, time)?
   ├── YES → Use Constrained Dijkstra (Template 2)
   └── NO → Use Basic Dijkstra (Template 1)

6. Need optimization for large graphs?
   ├── YES → Consider Bidirectional Dijkstra (Template 5)
   └── NO → Use selected template from above

When to Use Dijkstra vs BFS

Decision rule: If every edge has the same cost (or cost is 1), use BFS — it’s simpler and O(V+E). The moment edges have different non-negative weights, use Dijkstra.

Common trap: Using Dijkstra (PQ) for problems like LC 279 Perfect Squares or LC 752 Open the Lock where all edges cost 1 — plain BFS is sufficient and faster.

0-1 BFS special case: If edges are weighted 0 or 1 only, use a deque — push weight-0 edges to front, weight-1 edges to back. O(V+E) like BFS, handles two weights correctly. Example: LC 2290 Minimum Obstacle Removal.

When Dijkstra does not apply ★★★★★Priority 5 of 5 — Must know — expect it in almost every loop

Everything Dijkstra does rests on one claim: the first time a node is popped, its value is final. That claim needs two things to be true, and every limitation below is one of them failing:

1. Extending a path can never make it better, and never reverses two arrivals. Adding an edge only raises a cost you are minimising (or only lowers a value you are maximising), and the same edge applied to two arrivals at a node keeps the better one better. + w with w ≥ 0, × p with 0 ≤ p ≤ 1, max and min all do. Then nothing popped later can beat what was popped first.
2. The node alone says where you are. If what you may do next depends on how you arrived (cells already used, stops left, keys held), then dist[node] throws away paths that are still needed.

“Maximise” is not the problem — the direction of change is. Dijkstra handles a maximum whenever extending a path can only make it worse and keeps two arrivals in the same order (condition 1 above):

The full rule, and the (node, state) fix for condition 2, are in shortest_path_comparison.md § D and § B.

Path with Maximum Gold — LC 1219

Key point — the answer is the longest simple path by collected gold, and each cell may be used once, so both conditions above fail at once: no dist[cell] can stand for “the best way to reach this cell”, because whichever path reached it first may have used up the cells the best path needs. Try every start and every simple path, marking a cell on the way in and restoring it on the way out; with at most 25 gold cells that is fast enough.

Reduces to: dfs.md § Template 9: Grid DFS with Restore (Backtracking), which holds the solution; the mark-lifetime trace is under backtrack.md § Template 9.

Dry run — “Dijkstra for max” (a max-heap on gold so far, each cell finalised on its first pop, every cell tried as the start) against backtracking. The greedy tops out at 7 under every tie-breaking order (all 720 were tried), so the failure is not a tie artefact:

grid = 1 2 1        cells: (0,0) (0,1) (0,2)
       1 2 1               (1,0) (1,1) (1,2)

start (0,0), max-heap + best[cell]:
  pop (0,0) gold 1   push (0,1)=3, (1,0)=2
  pop (0,1) gold 3   <- 3 beats 2 outright; (0,1) is now FINAL
                        with the path (0,0)->(0,1)
  pop (1,1) gold 5, (1,0) gold 6, (1,2) gold 6, (0,2) gold 7
  best from this start: 7

backtracking            -> 8   (0,0) -> (1,0) -> (1,1) -> (0,1) -> (0,2) -> (1,2)
                               reaches (0,1) FOURTH, through a longer path that
                               best[(0,1)] had already ruled out

Traps

• A max-heap with best[cell] passes both of the problem’s own examples (24 and 28) and fails on the 2×3 grid above, whatever the tie order: correct on the samples is not evidence the greedy holds.
• Complexity is O(k · 3^k) for k gold cells, not polynomial: after the first step each cell has at most 3 unvisited neighbours. It is the constraint (k ≤ 25) that makes it pass, so say so in the interview.

Algorithm Comparison: Dijkstra vs Floyd-Warshall vs Bellman-Ford

The comparison with the other shortest-path algorithms — complexity, negative weights, early exit, path reconstruction, and which one a given situation calls for — lives in one place: shortest_path_comparison.md § Side-by-Side Comparison and § Scenario → Algorithm. The one-line version for this sheet: Dijkstra is the default for a single source with non-negative weights; a negative weight or a hop limit sends you to Bellman-Ford, every pair on a small graph to Floyd-Warshall, and equal weights to BFS (above).

Summary & Quick Reference

Complexity Quick Reference

Template Quick Reference

Common Patterns & Tricks

Priority Queue State

# Basic state
(distance, node)

# With constraints
(cost, node, stops_remaining)

# Grid problems
(cost, row, col)

# With path tracking
(distance, node, path)

Visited Set Optimization

# Option 1: Check after pop (recommended)
if node in visited:
    continue
visited.add(node)

# Option 2: Check distance
if d > dist[node]:
    continue

Path Reconstruction

parent = {}
# During relaxation:
parent[v] = u

# Reconstruct path:
path = []
while node != source:
    path.append(node)
    node = parent[node]
path.reverse()

Problem-Solving Steps

1. Identify graph structure: Explicit edges or implicit (grid)?
2. Check constraints: Non-negative weights? Single source?
3. Choose template: Basic, constrained, grid, or multi-source?
4. Define state: What needs tracking in priority queue?
5. Implement relaxation: How to update distances?
6. Handle termination: When to stop? Return what value?

Similar LeetCode Problems Reference

Grid-Based Problems

LC 1631 Deep Dive:

• Solutions Available: 4 major approaches (Dijkstra dist[], Dijkstra visited, Binary Search, Union Find)
• Most Common: Dijkstra with dist[][] array or visited[] array
• Key Insight: The cost model is Math.max(effort, step_diff), not additive—this makes DP impossible
• Reference: leetcode_java/src/main/java/LeetCodeJava/Graph/PathWithMinimumEffort.java (V0-V4.3)

Classic Shortest Path Problems

Multi-Source Shortest Path

Key Implementation Files

• Java Reference: leetcode_java/src/main/java/LeetCodeJava/DynamicProgramming/MinimumPathSum.java
  • V0: Dijkstra with dist[][] (works but overkill)
  • V0-0-1, V1, V2: Pure DP approaches (optimal for LC 64)
• Python Reference: leetcode_python/Dynamic_Programming/minimum-path-sum.py
  • V0-1, V0-2: Dijkstra (min-heap + cost_grid[][]) — see 7) LC 64
  • V1, V2: DP in-place O(1) space / 1D rolling row (optimal for LC 64)

Common Mistakes & Tips

🚫 Common Mistakes:

• Forgetting to check if already visited
• Using Dijkstra with negative weights
• Not using priority queue (using regular queue)
• Incorrect state comparison in constrained problems
• Not handling disconnected components

✅ Best Practices:

• Always use min-heap for priority queue
• Track visited nodes to avoid reprocessing
• Initialize distances to infinity except source
• Consider using distance array vs visited set
• Handle edge cases (empty graph, no path)

Interview Tips

1. Clarify constraints: Always ask about negative weights
2. State complexity: Mention time/space complexity upfront
3. Explain relaxation: Core concept of updating distances
4. Consider alternatives: Mention when BFS or Bellman-Ford better
5. Optimize if needed: Discuss bidirectional search for large graphs

Related Topics

• BFS: Unweighted shortest path
• Bellman-Ford: Handles negative weights (see detailed comparison above)
• Floyd-Warshall: All-pairs shortest path (see detailed comparison above)
• A Algorithm*: Heuristic-guided search
• SPFA: Queue-optimized Bellman-Ford variant
• Johnson’s Algorithm: All-pairs with reweighting technique