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

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. Is it a shortest path problem?
   ├── NO → Consider other algorithms (DFS, BFS, DP)
   └── YES → Continue to 2

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

Shortest Path Algorithm Selection:

1. What type of problem?
   ├── All-pairs shortest path? → Continue to 2
   │   ├── Small graph (V ≤ 400)? → Use Floyd-Warshall
   │   └── Large graph? → Run Dijkstra V times (or Johnson's algorithm)
   │
   └── Single-source shortest path? → Continue to 3

2. Are edge weights non-negative?
   ├── YES → Use Dijkstra (most efficient)
   │   ├── Sparse graph? → Dijkstra with binary heap: O((V+E) log V)
   │   └── Dense graph? → Consider array-based: O(V²)
   │
   └── NO (has negative weights) → Use Bellman-Ford
       └── Need cycle detection? → Bellman-Ford explicitly detects

3. Special cases:
   ├── Unweighted graph? → Use BFS: O(V+E)
   ├── Tree structure? → Use DFS/BFS: O(V)
   ├── Grid-based? → Dijkstra on implicit graph
   └── Transitive closure? → Floyd-Warshall (boolean variant)

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