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

Bài 13.2 - Phân tích độ phức tạp Dijkstra trong Python

Sau khi đã học cách cài đặt thuật toán Dijkstra với heapq, bây giờ chúng ta sẽ đi sâu vào phân tích độ phức tạp thời gian và bộ nhớ của thuật toán này, để hiểu vì sao nó lại hiệu quả và khi nào nó phù hợp.

Tóm tắt lại thuật toán Dijkstra

• Áp dụng cho đồ thị có trọng số không âm
• Tìm khoảng cách ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác
• Sử dụng hàng đợi ưu tiên (min-heap) để ưu tiên đỉnh có khoảng cách nhỏ nhất

Cài đặt nhắc lại bằng heapq

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]

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

        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

Các yếu tố ảnh hưởng đến độ phức tạp

• V: số đỉnh trong đồ thị
• E: số cạnh trong đồ thị
• heapq là min-heap – mất O(log V) cho mỗi thao tác push và pop

Phân tích độ phức tạp thời gian

Tổng thể: O((V + E) × log V)

Tức là với đồ thị thưa (sparse), thuật toán chạy rất hiệu quả.

So sánh với cài đặt không dùng heap

Nếu bạn dùng danh sách thường để tìm đỉnh gần nhất:

def get_min_node(distances, visited):
    min_node = None
    min_dist = float('inf')
    for node in distances:
        if node not in visited and distances[node] < min_dist:
            min_dist = distances[node]
            min_node = node
    return min_node

Độ phức tạp sẽ là: O(V²)

Vì mỗi lần bạn phải quét toàn bộ danh sách để chọn đỉnh gần nhất.

Ví dụ minh hoạ tốc độ

Đồ thị 1: Nhỏ (4 đỉnh)

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

Chạy Dijkstra bằng heapq sẽ chỉ mất vài ms.

Đồ thị 2: Lớn (1000 đỉnh, mỗi đỉnh nối 2 đỉnh kế tiếp)

graph = {i: [(i + 1, 1), (i + 2, 1)] for i in range(998)}
graph[998] = [(999, 1)]
graph[999] = []

# Gọi Dijkstra
dijkstra(graph, 0)

• Với heap: chạy nhanh, mượt
• Nếu không dùng heap: cực kỳ chậm

Phân tích bộ nhớ

Khi nào không nên dùng Dijkstra?

• Đồ thị có trọng số âm → dùng Bellman-Ford
• Cần tìm đường đi tốt nhất tới một đích duy nhất → có thể dùng A*

Tổng kết

• Thuật toán Dijkstra khi dùng với heapq có độ phức tạp tối ưu là O((V + E) × log V)
• Cần hiểu rõ heap giúp tối ưu hoá phần chọn đỉnh gần nhất
• Cài đặt đơn giản nhưng cực kỳ hiệu quả cho đồ thị lớn, không trọng số âm