Thuật toán Dijkstra

Khái niệm

Dijkstra là thuật toán tìm đường đi ngắn nhất từ một nguồn (Single Source Shortest Path — SSSP) cho đồ thị có trọng số không âm.

Ý tưởng: Dùng min-heap (hàng đợi ưu tiên) — liên tục chọn đỉnh chưa xử lý có khoảng cách nhỏ nhất, rồi “thư giãn” (relax) các cạnh kề.

Điều kiện áp dụng: Mọi trọng số cạnh ≥ 0. (Nếu có trọng số âm → dùng Bellman-Ford)

Cài đặt	Độ phức tạp
Ma trận kề (không heap)	O(V²)
Danh sách kề + min-heap	O((V + E) log V)

graph LR; S((S\ndist=0)) -- 4 --> A((A)); S -- 1 --> C((C)); C -- 2 --> A; C -- 5 --> B((B)); A -- 1 --> B; A -- 3 --> T((T\nđích)); B -- 2 --> T;

Từ S: S→C (1) → C→A (3) → A→T (6) là đường ngắn nhất. Không đi S→A trực tiếp vì tổng 4 > 3.

Cài đặt với min-heap

import heapq
from collections import defaultdict

def dijkstra(n, graph, src):
    """
    Tìm khoảng cách ngắn nhất từ src đến tất cả đỉnh còn lại.

    graph: dict {u: [(v, w), ...]} — danh sách kề có trọng số
    src  : đỉnh xuất phát (0-indexed)

    Trả về: dist[] — dist[v] là khoảng cách ngắn nhất từ src đến v
    """
    INF  = float('inf')
    dist = [INF] * n
    dist[src] = 0
    heap = [(0, src)]    # (khoảng_cách, đỉnh)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:   # Đã tìm được đường ngắn hơn trước đó → bỏ qua
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist


# Đồ thị ví dụ: 6 đỉnh (0=S, 1=A, 2=B, 3=C, 4=D, 5=T)
edges = [(0,1,4),(0,3,1),(3,1,2),(3,2,5),(1,2,1),(1,5,3),(2,5,2)]
g = defaultdict(list)
for u, v, w in edges:
    g[u].append((v, w))
    g[v].append((u, w))

dist = dijkstra(6, g, src=0)
print("Khoảng cách từ đỉnh 0:")
for v, d in enumerate(dist):
    print(f"  → đỉnh {v}: {d}")

Khôi phục đường đi

import heapq
from collections import defaultdict

def dijkstra_voi_duong_di(n, graph, src):
    """
    Dijkstra kèm truy vết đường đi.
    Trả về (dist[], prev[]) — prev[v] là đỉnh liền trước v trên đường ngắn nhất.
    """
    INF  = float('inf')
    dist = [INF] * n
    prev = [-1]  * n
    dist[src] = 0
    heap = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))

    return dist, prev

def lay_duong_di(prev, dst):
    """Truy vết từ mảng prev để lấy đường đi đến dst."""
    path = []
    cur  = dst
    while cur != -1:
        path.append(cur)
        cur = prev[cur]
    return path[::-1]

# Test
edges = [(0,1,4),(0,3,1),(3,1,2),(3,2,5),(1,2,1),(1,5,3),(2,5,2)]
g = defaultdict(list)
for u, v, w in edges:
    g[u].append((v, w))
    g[v].append((u, w))

dist, prev = dijkstra_voi_duong_di(6, g, src=0)
print(f"Khoảng cách 0→5: {dist[5]}")          # 6
print(f"Đường đi 0→5: {lay_duong_di(prev, 5)}")   # [0, 3, 1, 5] hoặc [0, 3, 1, 2, 5]

Bài tập luyện tập

Dễ — Khoảng cách ngắn nhất giữa hai đỉnh

import heapq
from collections import defaultdict

def khoang_cach_ngan_nhat(n, canh, src, dst):
    """Tìm khoảng cách ngắn nhất từ src đến dst, -1 nếu không tới được."""
    g = defaultdict(list)
    for u, v, w in canh:
        g[u].append((v, w))
        g[v].append((u, w))
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if u == dst:
            return d
        if d > dist[u]:
            continue
        for v, w in g[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return -1 if dist[dst] == float('inf') else dist[dst]

canh = [(0,1,7),(0,2,9),(0,5,14),(1,2,10),(1,3,15),(2,3,11),(2,5,2),(3,4,6),(4,5,9)]
print(khoang_cach_ngan_nhat(6, canh, 0, 4))    # 20

Trung bình — Đường đi ngắn nhất trên lưới có chướng ngại vật

import heapq

def dijkstra_luoi(luoi):
    """
    Tìm đường đi ngắn nhất từ (0,0) đến (rows-1,cols-1).
    Ô '#' là tường. Ô khác có chi phí = giá trị số tại ô đó.
    """
    rows, cols = len(luoi), len(luoi[0])
    INF  = float('inf')
    dist = [[INF] * cols for _ in range(rows)]
    dist[0][0] = luoi[0][0]
    heap = [(luoi[0][0], 0, 0)]

    while heap:
        d, r, c = heapq.heappop(heap)
        if d > dist[r][c]:
            continue
        if r == rows-1 and c == cols-1:
            return d
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and luoi[nr][nc] != '#':
                nd = dist[r][c] + luoi[nr][nc]
                if nd < dist[nr][nc]:
                    dist[nr][nc] = nd
                    heapq.heappush(heap, (nd, nr, nc))
    return -1

grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print(dijkstra_luoi(grid))   # 7 (1→3→1→1→1)

Khó — K đường đi ngắn nhất

import heapq
from collections import defaultdict

def k_duong_ngan_nhat(n, canh_co_huong, src, dst, k):
    """
    Tìm khoảng cách của đường đi ngắn thứ k từ src đến dst.
    Ý tưởng: mỗi đỉnh được "giải quyết" tối đa k lần.
    """
    g = defaultdict(list)
    for u, v, w in canh_co_huong:
        g[u].append((v, w))

    count = [0] * n   # Số lần đỉnh được lấy ra khỏi heap
    heap  = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        count[u] += 1
        if u == dst and count[u] == k:
            return d
        if count[u] > k:
            continue
        for v, w in g[u]:
            heapq.heappush(heap, (d + w, v))
    return -1   # Không đủ k đường đi

canh = [(0,1,1),(0,2,3),(1,3,2),(2,3,1),(1,2,1)]
print(k_duong_ngan_nhat(4, canh, 0, 3, 1))   # 3 (0→1→3)
print(k_duong_ngan_nhat(4, canh, 0, 3, 2))   # 4 (0→1→2→3)
print(k_duong_ngan_nhat(4, canh, 0, 3, 3))   # 4 (0→2→3 cũng là 4)

Kết luận

Dijkstra là thuật toán đường ngắn nhất mạnh nhất khi không có trọng số âm. Khi có trọng số âm, cần dùng Bellman-Ford. Sau khi nắm cả hai, hãy học Cây khung nhỏ nhất (MST).

Trong series này: