Dijkstra’s Algorithm

Movement: RIGHT only ↓ or DOWN only →

// 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))

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

// 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)

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

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

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

# 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

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

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

# 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))

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

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

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])

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

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

# Basic state
(distance, node)

# With constraints
(cost, node, stops_remaining)

# Grid problems
(cost, row, col)

# With path tracking
(distance, node, path)

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

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

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

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