Shortest Path Patterns¶

def shortest_path(graph, start, end):
    """
    Generic shortest path framework.

    Components:
    1. Distance array: dist[node] = minimum cost to reach node
    2. Priority structure: heap (Dijkstra) or deque (0-1 BFS)
    3. Relaxation: if new_cost < dist[neighbor], update
    """
    dist = {start: 0}  # or [inf] * n with dist[start] = 0
    pq = [(0, start)]  # (cost, node)

    while pq:
        cost, node = heappop(pq)

        if cost > dist.get(node, inf):
            continue  # Already found better path

        if node == end:
            return cost

        for neighbor, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist.get(neighbor, inf):
                dist[neighbor] = new_cost
                heappush(pq, (new_cost, neighbor))

    return -1  # Unreachable

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        """
        Dijkstra's algorithm for single-source shortest paths.

        Time: O((V + E) log V) with binary heap
        Space: O(V + E)
        """
        from heapq import heappush, heappop

        # Build adjacency list
        graph: Dict[int, List[Tuple[int, int]]] = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        # Dijkstra's algorithm
        dist: Dict[int, int] = {}
        pq: List[Tuple[int, int]] = [(0, k)]  # (distance, node)

        while pq:
            d, node = heappop(pq)

            if node in dist:
                continue  # Already processed

            dist[node] = d

            for neighbor, weight in graph[node]:
                if neighbor not in dist:
                    heappush(pq, (d + weight, neighbor))

        # Check if all nodes reachable
        if len(dist) != n:
            return -1

        return max(dist.values())

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        """
        Dijkstra's algorithm with minimax objective.

        Key change: dist[node] = min(max edge weight on any path to node)

        Time: O(mn log(mn))
        Space: O(mn)
        """
        from heapq import heappush, heappop

        rows, cols = len(heights), len(heights[0])

        # dist[r][c] = minimum effort to reach (r, c)
        dist = [[float('inf')] * cols for _ in range(rows)]
        dist[0][0] = 0

        # (effort, row, col)
        pq: List[Tuple[int, int, int]] = [(0, 0, 0)]
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while pq:
            effort, r, c = heappop(pq)

            if effort > dist[r][c]:
                continue

            if r == rows - 1 and c == cols - 1:
                return effort

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    # Edge weight = absolute height difference
                    edge_effort = abs(heights[nr][nc] - heights[r][c])
                    # New effort = max(path effort so far, this edge)
                    new_effort = max(effort, edge_effort)

                    if new_effort < dist[nr][nc]:
                        dist[nr][nc] = new_effort
                        heappush(pq, (new_effort, nr, nc))

        return dist[rows - 1][cols - 1]

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]],
                          src: int, dst: int, k: int) -> int:
        """
        Modified Dijkstra with state = (node, stops_used).

        Time: O(E * K * log(E * K))
        Space: O(N * K)
        """
        from heapq import heappush, heappop

        # Build graph
        graph: Dict[int, List[Tuple[int, int]]] = defaultdict(list)
        for u, v, price in flights:
            graph[u].append((v, price))

        # dist[node][stops] = min cost to reach node using exactly stops edges
        # We track minimum cost for each (node, stops) state
        dist: Dict[Tuple[int, int], int] = {}

        # (cost, node, stops_used)
        pq: List[Tuple[int, int, int]] = [(0, src, 0)]

        while pq:
            cost, node, stops = heappop(pq)

            if node == dst:
                return cost

            if stops > k:
                continue  # Too many stops

            if (node, stops) in dist and dist[(node, stops)] <= cost:
                continue

            dist[(node, stops)] = cost

            for neighbor, price in graph[node]:
                new_cost = cost + price
                new_stops = stops + 1

                # Only continue if we haven't found a better path to this state
                if (neighbor, new_stops) not in dist:
                    heappush(pq, (new_cost, neighbor, new_stops))

        return -1

class SolutionBellmanFord:
    def findCheapestPrice(self, n: int, flights: List[List[int]],
                          src: int, dst: int, k: int) -> int:
        """
        Bellman-Ford: Relax all edges k+1 times.

        Time: O(K * E)
        Space: O(N)
        """
        INF = float('inf')
        dist = [INF] * n
        dist[src] = 0

        # Relax edges k+1 times (k stops = k+1 edges)
        for _ in range(k + 1):
            # Use copy to avoid using updated values in same iteration
            new_dist = dist.copy()

            for u, v, price in flights:
                if dist[u] != INF:
                    new_dist[v] = min(new_dist[v], dist[u] + price)

            dist = new_dist

        return dist[dst] if dist[dst] != INF else -1

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        """
        0-1 BFS: Deque-based shortest path for binary edge weights.

        Time: O(mn)
        Space: O(mn)
        """
        from collections import deque

        rows, cols = len(grid), len(grid[0])

        # Direction mapping: 1=right, 2=left, 3=down, 4=up
        directions = {
            1: (0, 1),   # right
            2: (0, -1),  # left
            3: (1, 0),   # down
            4: (-1, 0)   # up
        }
        all_dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        dir_to_num = {(0, 1): 1, (0, -1): 2, (1, 0): 3, (-1, 0): 4}

        dist = [[float('inf')] * cols for _ in range(rows)]
        dist[0][0] = 0

        dq: Deque[Tuple[int, int, int]] = deque([(0, 0, 0)])  # (cost, row, col)

        while dq:
            cost, r, c = dq.popleft()

            if cost > dist[r][c]:
                continue

            if r == rows - 1 and c == cols - 1:
                return cost

            current_arrow = grid[r][c]

            for dr, dc in all_dirs:
                nr, nc = r + dr, c + dc

                if 0 <= nr < rows and 0 <= nc < cols:
                    # Cost 0 if this direction matches the arrow
                    edge_cost = 0 if dir_to_num[(dr, dc)] == current_arrow else 1
                    new_cost = cost + edge_cost

                    if new_cost < dist[nr][nc]:
                        dist[nr][nc] = new_cost

                        if edge_cost == 0:
                            dq.appendleft((new_cost, nr, nc))  # Front for cost 0
                        else:
                            dq.append((new_cost, nr, nc))      # Back for cost 1

        return dist[rows - 1][cols - 1]

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        """
        0-1 BFS: Cost = grid value (0 for empty, 1 for obstacle).

        Time: O(mn)
        Space: O(mn)
        """
        from collections import deque

        rows, cols = len(grid), len(grid[0])

        dist = [[float('inf')] * cols for _ in range(rows)]
        dist[0][0] = 0

        dq: Deque[Tuple[int, int, int]] = deque([(0, 0, 0)])  # (cost, row, col)
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while dq:
            cost, r, c = dq.popleft()

            if cost > dist[r][c]:
                continue

            if r == rows - 1 and c == cols - 1:
                return cost

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                if 0 <= nr < rows and 0 <= nc < cols:
                    # Cost to enter cell = grid value (0 or 1)
                    new_cost = cost + grid[nr][nc]

                    if new_cost < dist[nr][nc]:
                        dist[nr][nc] = new_cost

                        if grid[nr][nc] == 0:
                            dq.appendleft((new_cost, nr, nc))  # Free move: front
                        else:
                            dq.append((new_cost, nr, nc))      # Remove obstacle: back

        return dist[rows - 1][cols - 1]

# Dijkstra approach (works but slower)
def dijkstra_version(grid):
    pq = [(0, 0, 0)]  # heap
    while pq:
        cost, r, c = heappop(pq)  # O(log n)
        ...
        heappush(pq, (new_cost, nr, nc))  # O(log n)

# 0-1 BFS approach (optimal)
def bfs_01_version(grid):
    dq = deque([(0, 0, 0)])  # deque
    while dq:
        cost, r, c = dq.popleft()  # O(1)
        ...
        if cost == 0:
            dq.appendleft(...)  # O(1)
        else:
            dq.append(...)  # O(1)

def bfs_01(grid):
    """
    0-1 BFS template for binary edge weights.
    """
    from collections import deque

    rows, cols = len(grid), len(grid[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = 0  # or cost of starting cell

    dq = deque([(initial_cost, 0, 0)])

    while dq:
        cost, r, c = dq.popleft()

        if cost > dist[r][c]:
            continue

        for nr, nc in neighbors(r, c):
            edge_cost = get_edge_cost(r, c, nr, nc)  # 0 or 1
            new_cost = cost + edge_cost

            if new_cost < dist[nr][nc]:
                dist[nr][nc] = new_cost
                if edge_cost == 0:
                    dq.appendleft((new_cost, nr, nc))
                else:
                    dq.append((new_cost, nr, nc))

    return dist[target_r][target_c]

def dijkstra(n: int, edges: List[Tuple[int, int, int]], src: int) -> List[int]:
    """
    Single-source shortest paths with non-negative weights.
    edges: List of (from, to, weight)

    Returns:
        dist[i] = shortest distance from src to i (-1 if unreachable)
    """
    from heapq import heappush, heappop
    from collections import defaultdict

    graph: Dict[int, List[Tuple[int, int]]] = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))

    dist: List[int] = [float('inf')] * n
    dist[src] = 0
    pq: List[Tuple[int, int]] = [(0, src)]  # (distance, node)

    while pq:
        d, node = heappop(pq)

        if d > dist[node]:
            continue  # Already found better path

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

    return [d if d != float('inf') else -1 for d in dist]

def bfs_01(grid: List[List[int]], start: Tuple[int, int],
           end: Tuple[int, int]) -> int:
    """
    Shortest path with binary edge weights (0 or 1).

    Returns:
        Minimum cost from start to end, or -1 if unreachable.
    """
    from collections import deque

    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    er, ec = end

    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[sr][sc] = 0

    dq: Deque[Tuple[int, int, int]] = deque([(0, sr, sc)])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while dq:
        cost, r, c = dq.popleft()

        if cost > dist[r][c]:
            continue

        if r == er and c == ec:
            return cost

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                # Define edge_cost based on problem
                edge_cost = grid[nr][nc]  # or custom logic
                new_cost = cost + edge_cost

                if new_cost < dist[nr][nc]:
                    dist[nr][nc] = new_cost
                    if edge_cost == 0:
                        dq.appendleft((new_cost, nr, nc))
                    else:
                        dq.append((new_cost, nr, nc))

    return -1 if dist[er][ec] == float('inf') else dist[er][ec]

def bellman_ford_k(n: int, edges: List[Tuple[int, int, int]],
                   src: int, k: int) -> List[int]:
    """
    Shortest paths with at most k edges.
    edges: List of (from, to, weight)

    Returns:
        dist[i] = shortest distance from src to i using <= k edges
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0

    for _ in range(k):
        new_dist = dist.copy()
        for u, v, w in edges:
            if dist[u] != INF:
                new_dist[v] = min(new_dist[v], dist[u] + w)
        dist = new_dist

    return [d if d != INF else -1 for d in dist]

def dijkstra_minimax(grid: List[List[int]]) -> int:
    """
    Find path minimizing the maximum edge weight.

    Returns:
        Minimum possible maximum edge weight from (0,0) to (m-1,n-1)
    """
    from heapq import heappush, heappop

    rows, cols = len(grid), len(grid[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = 0

    pq: List[Tuple[int, int, int]] = [(0, 0, 0)]  # (max_weight, row, col)
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while pq:
        max_w, r, c = heappop(pq)

        if max_w > dist[r][c]:
            continue

        if r == rows - 1 and c == cols - 1:
            return max_w

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                edge_weight = abs(grid[nr][nc] - grid[r][c])
                new_max = max(max_w, edge_weight)

                if new_max < dist[nr][nc]:
                    dist[nr][nc] = new_max
                    heappush(pq, (new_max, nr, nc))

    return dist[rows - 1][cols - 1]