Khóa học Python từ Cơ bản đến Nâng cao

Bài 13.1 - Thuật toán Dijkstra với Python sử dụng heapq

Dijkstra là thuật toán nổi tiếng dùng để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị có trọng số không âm.

Trong Python, ta có thể kết hợp thuật toán Dijkstra với thư viện heapq để cải thiện tốc độ nhờ vào priority queue (hàng đợi ưu tiên).

Ý tưởng cơ bản

1. Sử dụng min-heap để luôn chọn đỉnh có khoảng cách ngắn nhất hiện tại.
2. Cập nhật khoảng cách tới các đỉnh kề nếu tìm được đường đi ngắn hơn.
3. Lặp lại cho đến khi duyệt hết toàn bộ các đỉnh.

Cấu trúc đồ thị

Ta sẽ dùng adjacency list, với mỗi đỉnh ánh xạ tới danh sách các cặp (đỉnh_kề, trọng_số).

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}

Cài đặt Dijkstra với heapq

import heapq

def dijkstra(graph, start):
    # Khởi tạo khoảng cách ban đầu: vô cùng
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # Min-heap: (khoảng cách, đỉnh)
    heap = [(0, start)]

    while heap:
        current_dist, current_node = heapq.heappop(heap)

        # Nếu tìm được đường đi ngắn hơn rồi thì bỏ qua
        if current_dist > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))

    return distances

Ví dụ minh hoạ

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}

distances = dijkstra(graph, 'A')
print("Khoảng cách từ A đến các đỉnh:", distances)

Kết quả:

Khoảng cách từ A đến các đỉnh: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Giải thích:

• A đến B: 1
• A → B → C: 1 + 2 = 3
• A → B → C → D: 1 + 2 + 1 = 4

Giải thích code

• distances: dictionary lưu khoảng cách ngắn nhất từ start đến các đỉnh.
• heap: giúp chọn đỉnh có khoảng cách nhỏ nhất nhanh chóng (O(log n)).
• Kiểm tra if current_dist > distances[current_node] để tránh xử lý lại đỉnh đã tối ưu.

Độ phức tạp

• V: số đỉnh
• E: số cạnh
• heapq giúp tối ưu thay vì tìm tuyến tính như Dijkstra truyền thống.

Gợi ý mở rộng

• Truy vết đường đi (không chỉ khoảng cách).
• Chạy Dijkstra từ nhiều điểm xuất phát.
• Áp dụng với bản đồ, game pathfinding, router networks.

Tổng kết

• Dijkstra + heapq là công cụ mạnh để tìm đường đi ngắn nhất trong đồ thị có trọng số không âm.
• Cài đặt đơn giản, dễ mở rộng và ứng dụng thực tế rất nhiều.
• Hiểu được thuật toán này là một bước quan trọng để học A*, Bellman-Ford, và các thuật toán mạng phức tạp hơn.