Chương 30 - Dijkstra

Dijkstra tìm đường đi ngắn nhất từ 1 source đến mọi đỉnh trong graph trọng số không âm. Khi cạnh có thể âm → Bellman-Ford. Khi cạnh đồng nhất (= 1) → BFS đủ rồi. Dijkstra với heap chạy O((V + E) log V).

Mục tiêu chương

Sau chương này, bạn sẽ:

• Dijkstra OK khi trọng số không âm; cạnh âm → Bellman-Ford.
• Lazy deletion: if d > dist[u]: continue thay priority update.
• 0-1 BFS với deque thay heap khi trọng số chỉ 0 hoặc 1.
• Cheapest Flights K Stops: Bellman-Ford k+1 lần thay vì Dijkstra.

Khi nào dùng pattern này?

• Graph có trọng số không âm, cần shortest path.
• Bài “minimum cost path”, “minimum effort”, “minimum sum to reach”.
• Khi BFS không đủ vì trọng số khác nhau.

Template code

import heapq
from collections import defaultdict

def dijkstra(graph: dict, source: int, n: int) -> list[float]:
    INF = float('inf')
    dist = [INF] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                # outdated entry
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Bài tự luyện cuối chương

• LC 882 - Reachable Nodes In Subdivided Graph
• LC 1976 - Number of Ways to Arrive at Destination
• LC 2065 - Maximum Path Quality

---

30.1 Network Delay Time (LC 743)

Đề bài

Cho times[i] = [u, v, w] (directed weighted), n đỉnh, source k. Tìm thời gian để tín hiệu đến tất cả đỉnh, hoặc -1.

Ví dụ

Input:  times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
Output: 2

Ràng buộc

• 1 <= k <= n <= 100
• 1 <= len(times) <= 6000
• 1 <= w <= 100

Clarifying questions

• Graph không liên thông? → Trả -1.
• Cạnh self-loop? → Theo đề: không.

Hướng tiếp cận

Dijkstra từ k. Đáp án = max của dist[].

Code Python 3

import heapq
from collections import defaultdict
from typing import List

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        INF = float('inf')
        dist = {i: INF for i in range(1, n + 1)}
        dist[k] = 0
        heap = [(0, k)]
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]: continue
            for v, w in graph[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(heap, (d + w, v))
        ans = max(dist.values())
        return ans if ans < INF else -1

Phân tích độ phức tạp

• Thời gian: O((V + E) log V).
• Bộ nhớ: O(V + E).

Bình luận

• Lazy deletion (if d > dist[u]: continue) là idiomatic - không cần priority update.

Bài tự luyện liên quan

• LC 787 - Cheapest Flights Within K Stops (bài 30.3).

---

30.2 Path With Minimum Effort (LC 1631)

Đề bài

Grid heights. Đi từ (0,0) đến (m-1,n-1) (4 hướng). Effort = max |h(u) - h(v)| qua các cạnh trên path. Tìm min effort.

Ví dụ

Input:  heights = [[1,2,2],
                   [3,8,2],
                   [5,3,5]]   (grid m×n, đi 4 hướng từ (0,0) → (m-1,n-1))
Output: 2   (effort min = max |h[u] - h[v]| trên path tốt nhất)

Ràng buộc

• 1 <= rows, cols <= 100
• 1 <= heights[r][c] <= 10^6

Clarifying questions

• Grid 1×1? → Trả 0.

• Có cạnh trọng số âm? → Effort =

  diff

  luôn ≥ 0.

Hướng tiếp cận

Dijkstra với “trọng số path” = max edge weight thay vì sum. nd = max(d, |h(u) - h(v)|).

Code Python 3

import heapq
from typing import List

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        INF = float('inf')
        effort = [[INF] * cols for _ in range(rows)]
        effort[0][0] = 0
        heap = [(0, 0, 0)]      # (effort, r, c)
        DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
        while heap:
            e, r, c = heapq.heappop(heap)
            if (r, c) == (rows - 1, cols - 1):
                return e
            if e > effort[r][c]: continue
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    ne = max(e, abs(heights[nr][nc] - heights[r][c]))
                    if ne < effort[nr][nc]:
                        effort[nr][nc] = ne
                        heapq.heappush(heap, (ne, nr, nc))
        return 0

Phân tích độ phức tạp

• Thời gian: O(R · C · log(R · C)).
• Bộ nhớ: O(R · C).

Bình luận

• Variant of Dijkstra với “max-aggregated path” thay vì “sum-aggregated”.
• Cũng giải được bằng Union Find (Chương 24.6) hoặc Binary Search + DFS (Chương 37).

Bài tự luyện liên quan

• LC 778 - Swim in Rising Water (Chương 24.6).

---

30.3 Cheapest Flights Within K Stops (LC 787)

Đề bài

Cho flights[i] = [u, v, price], n đỉnh, source src, dest dst, k stops. Tìm cheapest flight ≤ k stops.

Ví dụ

Input:  n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
Output: 200

Ràng buộc

• 1 <= n <= 100
• 0 <= flights.length <= n·(n-1)/2

Clarifying questions

• k = 0? → Direct flight only.
• Không có path? → Trả -1.

Hướng tiếp cận

Bellman-Ford với k + 1 lần lặp là cách gọn nhất.

Dijkstra cũng giải được, nhưng state phải mở rộng thành (cost, node, stops) - phức tạp hơn vì state có 2 chiều.

Code Python 3

from typing import List

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        INF = float('inf')
        dist = [INF] * n
        dist[src] = 0
        for _ in range(k + 1):
            new_dist = dist.copy()
            for u, v, p in flights:
                if dist[u] + p < new_dist[v]:
                    new_dist[v] = dist[u] + p
            dist = new_dist
        return dist[dst] if dist[dst] < INF else -1

Phân tích độ phức tạp

• Thời gian: O(k · E) (Bellman-Ford k+1 iterations).
• Bộ nhớ: O(V).

Bình luận

• Bellman-Ford k+1 lần = relax tất cả edge k+1 lượt → đảm bảo path ≤ k+1 edges = k stops.
• Bẫy new_dist: phải dùng copy để không “lan toả” trong cùng 1 lượt.

Bài tự luyện liên quan

• LC 1928 - Minimum Cost to Reach Destination in Time.

---

30.4 Swim in Rising Water (LC 778) - recap

Đã giải đầy đủ ở Chương 24.6 (DSU offline). Cũng giải được bằng Dijkstra: trọng số path = max elevation gặp phải.

Code Python 3

import heapq
class Solution:
    def swimInWater(self, grid):
        n = len(grid)
        dist = [[float('inf')] * n for _ in range(n)]
        dist[0][0] = grid[0][0]
        heap = [(grid[0][0], 0, 0)]
        DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
        while heap:
            d, r, c = heapq.heappop(heap)
            if (r, c) == (n-1, n-1): return d
            for dr, dc in DIRS:
                nr, nc = r+dr, c+dc
                if 0 <= nr < n and 0 <= nc < n:
                    nd = max(d, grid[nr][nc])
                    if nd < dist[nr][nc]:
                        dist[nr][nc] = nd
                        heapq.heappush(heap, (nd, nr, nc))
        return -1

Phân tích độ phức tạp

• Thời gian: O((V + E) log V).
• Bộ nhớ: O(V + E).

Bài tự luyện liên quan

• LC 1631 - Path With Minimum Effort.

---

30.5 Shortest Path in a Grid with Obstacles Elimination (LC 1293)

Đề bài

Input: grid: List[List[int]] (m × n, 0 = ô trống đi được, 1 = vật cản) và số nguyên k. Đi 4 hướng từ (0,0) → (m-1, n-1), được phá tối đa k vật cản. Tìm shortest path từ (0,0) đến (m-1,n-1).

Ví dụ

Input:  grid=[[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k=1
Output: 6

Ràng buộc

• 1 <= m, n <= 40
• 1 <= k <= m·n

Clarifying questions

• k đủ lớn để phá hết vật cản? → Optimization shortcut return rows+cols-2.

Hướng tiếp cận

BFS với state (r, c, eliminations_left) (vì cạnh trọng số 1). Dijkstra cũng được nhưng overkill.

Code Python 3

from collections import deque
from typing import List

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        rows, cols = len(grid), len(grid[0])
        if rows == 1 and cols == 1: return 0
        # Optimization: k đủ lớn → BFS thuần.
        if k >= rows + cols - 2:
            return rows + cols - 2

        visited = set([(0, 0, k)])
        queue = deque([(0, 0, k, 0)])    # (r, c, eliminations, steps)
        DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
        while queue:
            r, c, e, steps = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if not (0 <= nr < rows and 0 <= nc < cols): continue
                ne = e - grid[nr][nc]
                if ne < 0: continue
                if (nr, nc) == (rows - 1, cols - 1): return steps + 1
                if (nr, nc, ne) not in visited:
                    visited.add((nr, nc, ne))
                    queue.append((nr, nc, ne, steps + 1))
        return -1

Phân tích độ phức tạp

• Thời gian: O(R · C · k) state với k = eliminations.
• Bộ nhớ: O(R · C · k).

Bình luận

• State 3D: thêm eliminations_left để tránh thăm trùng.

Bài tự luyện liên quan

• LC 1091 - Shortest Path in Binary Matrix.

---

30.6 Minimum Cost to Make at Least One Valid Path in a Grid (LC 1368)

Đề bài

Grid với mũi tên ở mỗi ô (4 hướng). Đi theo mũi tên free; đổi mũi tên cost 1. Tìm cost min để có path từ (0,0) đến (m-1,n-1).

Ví dụ

Input:  grid = [[1,1,1,1],
                [2,2,2,2],
                [1,1,1,1],
                [2,2,2,2]]
        (1=right, 2=left, 3=down, 4=up; theo mũi tên free, đổi cost 1)
Output: 3   (cần đổi 3 ô để có path hợp lệ từ (0,0) tới (m-1,n-1))

Ràng buộc

• 1 <= m, n <= 100
• grid[i][j] ∈ {1, 2, 3, 4}

Clarifying questions

• Grid 1×1? → Trả 0 (đã ở target).

Hướng tiếp cận

0-1 BFS (Dijkstra với deque): - Cạnh “đi theo mũi tên” = 0 → đẩy vào đầu deque. - Cạnh “đổi mũi tên” = 1 → đẩy vào cuối.

O(V + E).

Code Python 3

from collections import deque
from typing import List

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        INF = float('inf')
        dist = [[INF] * cols for _ in range(rows)]
        dist[0][0] = 0
        # 1: right, 2: left, 3: down, 4: up
        DIRS = {1: (0,1), 2: (0,-1), 3: (1,0), 4: (-1,0)}
        dq = deque([(0, 0, 0)])      # (cost, r, c)
        while dq:
            cost, r, c = dq.popleft()
            if cost > dist[r][c]: continue
            for d, (dr, dc) in DIRS.items():
                nr, nc = r + dr, c + dc
                if not (0 <= nr < rows and 0 <= nc < cols): continue
                nc_cost = cost + (0 if grid[r][c] == d else 1)
                if nc_cost < dist[nr][nc]:
                    dist[nr][nc] = nc_cost
                    if grid[r][c] == d:
                        dq.appendleft((nc_cost, nr, nc))
                    else:
                        dq.append((nc_cost, nr, nc))
        return dist[rows - 1][cols - 1]

Phân tích độ phức tạp

• Thời gian: O(V + E) (0-1 BFS với deque).
• Bộ nhớ: O(V).

Bình luận

• 0-1 BFS là special case của Dijkstra với cạnh chỉ là 0 hoặc 1 → deque thay heap, O(V + E).

Bài tự luyện liên quan

• LC 2290 - Minimum Obstacle Removal to Reach Corner.

Tóm tắt chương & Quyết định

Shortest path algorithm chooser

Tính chất đồ thị	Thuật toán	Time
Unweighted (mọi cạnh = 1)	BFS	O(V + E)
Edge weight ∈ {0, 1}	0-1 BFS (deque, push_front cho 0, push_back cho 1)	O(V + E)
Edge weight ≥ 0	Dijkstra (heap)	O((V + E) log V)
Có cạnh âm, không vòng âm	Bellman-Ford	O(V · E)
Có cạnh âm, cần detect vòng âm	Bellman-Ford + check vòng V	O(V · E)
All-pairs, V ≤ 500	Floyd-Warshall	O(V³)
DAG	Topo + relax	O(V + E)

Cheapest Flights with K Stops (LC 787)

• Không dùng Dijkstra thuần vì state cần thêm “số stops”.
• Cách 1: BFS theo level (mỗi level = 1 stop), giữ dist[node].
• Cách 2: Bellman-Ford K+1 vòng (mỗi vòng relax ≤ 1 cạnh thêm).

Minimum Cost Valid Path (LC 1368) - 0-1 BFS

• Cạnh “đi theo hướng cho trước” = 0 cost; đổi hướng = 1 cost.
• Deque: push_front khi cost = 0, push_back khi cost = 1.
• O(R · C), không cần log của heap.

---