Thuật toán Dijkstra là gì: cách hoạt động, code và độ phức tạp

Thuật toán Dijkstra giải bài toán gì

Duyệt theo chiều rộng tìm đường đi có ít cạnh nhất, nhưng đường bộ, liên kết mạng hay chuyến bay lại có độ dài, chi phí hoặc độ trễ khác nhau. Thuật toán Dijkstra giải bài toán đường đi ngắn nhất từ một nguồn trên các đồ thị có trọng số như vậy: cho một nút xuất phát, tìm tổng chi phí rẻ nhất để đến mọi nút khác, cùng đường đi đạt được chi phí đó.

Edsger W. Dijkstra công bố thuật toán vào năm 1959 trong bài báo “A note on two problems in connexion with graphs”.

Ý tưởng bằng lời đơn giản

1. Đặt khoảng cách của nút xuất phát là 0 và khoảng cách của mọi nút khác là vô cùng.
2. Chọn nút chưa chốt có khoảng cách nhỏ nhất. Khoảng cách của nó từ giờ là cuối cùng.
3. Nới lỏng từng cạnh đi ra u → v có trọng số w: nếu dist[u] + w < dist[v] thì gán dist[v] = dist[u] + w và ghi nhớ u là nút cha của v.
4. Lặp lại bước 2 và 3 cho đến khi mọi nút có thể tới được đều đã chốt.

Vì sao khoảng cách nhỏ nhất là cuối cùng? Mọi đường khác đến nút đó đều phải đi qua một nút có khoảng cách ít nhất bằng nó, và với trọng số không âm, các cạnh còn lại chỉ có thể làm tăng chi phí.

Ví dụ từng bước

Đồ thị có hướng với các cạnh A→B (4), A→C (1), C→B (2), B→D (1), C→D (5), D→E (3). Bắt đầu từ A.

Đầu tiên B có khoảng cách 4 từ cạnh trực tiếp, sau đó được cải thiện xuống 3 qua C. Đường đi ngắn nhất đến E là A → C → B → D → E với tổng chi phí 1 + 2 + 1 + 3 = 7.

Cài đặt bằng Python với heapq

Module heapq của Python cung cấp min-heap nhị phân. Thay vì thao tác “decrease key”, hãy đẩy một cặp (distance, node) mới mỗi khi khoảng cách được cải thiện và bỏ qua các cặp đã lỗi thời khi lấy ra. Kỹ thuật này gọi là xóa lười (lazy deletion).

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
graph = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}
dist, parent = dijkstra(graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

Để lấy đường đi đến một đích, lần theo các liên kết nút cha ngược về điểm xuất phát:

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(parent, "E"))  # ['A', 'C', 'B', 'D', 'E']

Nếu chỉ cần khoảng cách đến một đích, bạn có thể dừng ngay khi đích đó được lấy ra khỏi heap: lúc ấy khoảng cách của nó đã là cuối cùng.

Độ phức tạp thời gian và không gian

Không gian là O(V + E) cho đồ thị, các bảng khoảng cách và nút cha, cùng heap.

Biến thể và lỗi thường gặp

• Quên kiểm tra if d > dist[u]: continue không làm sai kết quả, nhưng khiến thuật toán xử lý cả các phần tử cũ và có thể chậm đi rất nhiều.
• Chỉ đẩy nút thay vì (distance, node) làm thứ tự trong heap trở nên vô nghĩa.
• Nếu các nút là đối tượng không so sánh được, khi khoảng cách bằng nhau heapq sẽ so sánh các nút và gây TypeError. Hãy đẩy (distance, counter, node) với một bộ đếm duy nhất.
• Tìm kiếm A* là Dijkstra có thêm hàm heuristic vào độ ưu tiên; nó duyệt ít nút hơn khi bạn có ước lượng tốt về khoảng cách còn lại.
• Dijkstra hai chiều chạy từ cả điểm xuất phát lẫn điểm đích và dừng khi hai lượt tìm kiếm gặp nhau.

Khi nào dùng và ứng dụng thực tế

• Định tuyến: các giao thức định tuyến trạng thái liên kết như OSPF và IS-IS chạy phép tính đường đi ngắn nhất trước (SPF) dựa trên thuật toán Dijkstra.
• Bản đồ và dẫn đường, nơi các hệ thống thực tế bổ sung bước tiền xử lý lên trên tìm kiếm kiểu Dijkstra.
• Bài phỏng vấn: network delay time, cheapest flights (có giới hạn số chặng dừng), path with minimum effort trên lưới, và mọi câu hỏi “tổng chi phí nhỏ nhất” trên đồ thị.