Thuật toán Dijkstra

Thuật toán Dijkstra là một thuật toán tìm đường đi ngắn nhất trong một đồ thị có trọng số dương. Thuật toán được phát minh bởi nhà toán học Edsger W. Dijkstra vào năm 1956.

Các bước thực hiện thuật toán

  1. Khởi tạo đồ thị và đặt khoảng cách ban đầu từ đỉnh bắt đầu đến các đỉnh khác là vô cùng.
  2. Đặt khoảng cách ban đầu của đỉnh bắt đầu là 0.
  3. Lặp lại cho tất cả các đỉnh trong đồ thị: a. Chọn đỉnh có khoảng cách tối thiểu từ đỉnh bắt đầu, đánh dấu đỉnh này là đã thăm. b. Cập nhật khoảng cách từ đỉnh bắt đầu đến các đỉnh kề của đỉnh đã chọn.
  4. Khi tất cả các đỉnh đều đã được thăm, thuật toán sẽ trả về khoảng cách từ đỉnh bắt đầu đến tất cả các đỉnh khác trong đồ thị.

Ví dụ về thuật toán

Giả sử bạn muốn đi từ đỉnh A đến đỉnh E trên đồ thị sau:

    6     2
A------B------C
|            / |
|   3     /    | 1
|      /       |
|  /           |
D-------------E
      2

Ta muốn tìm đường đi từ A đến E sao cho tổng trọng số trên đường đi là nhỏ nhất.

  • Bước 1: Khởi tạo dist ban đầu là vô cùng. Đặt chi phí đi từ A đến chính nó bằng 0. Lúc này dist = {A: 0, B: inf, C: inf, D: inf, E: inf}.
  • Bước 2: Bắt đầu từ đỉnh A, duyệt tất cả các đỉnh có thể kề với A (trong trường hợp này là B và D). Cập nhật lại khoảng cách dist[v] của các đỉnh kề với A. Vì đỉnh B và D kề với A, nên dist[B] = 6 (chi phí đi từ A đến B là 6), dist[D] = 3 (chi phí đi từ A đến D là 3).
  • Bước 3: Chọn đỉnh có khoảng cách nhỏ nhất từ đỉnh A (trong trường hợp này là D). Duyệt tất cả các đỉnh có thể kề với D (trong trường hợp này là A, B, E). Cập nhật lại khoảng cách dist[v] của các đỉnh kề với D. Vì chỉ có đỉnh B và E có thể kề với D, nên dist[B] = 5 (chi phí đi từ A đến D rồi đi từ D đến B là 3 + 2 = 5), dist[E] = 5 (chi phí đi từ A đến D rồi đi từ D đến E là 3 + 2 = 5).
  • Bước 4: Chọn đỉnh có khoảng cách nhỏ nhất từ đỉnh A (trong trường hợp này vẫn là D vì dist[D] = 3 < dist[B] = 5 và dist[E] = 5). Duyệt tất cả các đỉnh có thể kề với D (trong trường hợp này là A, B, E, C). Cập nhật lại khoảng cách dist[v] của các đỉnh kề với D. Vì chỉ có đỉnh B và E có thể kề với D, nên dist[E] = 4 (chi phí đi từ A đến D rồi đi từ D đến E là 3 + 1 = 4).
  • Bước 5: Chọn đỉnh có khoảng cách nhỏ nhất từ đỉnh A (trong trường hợp này là E vì dist[E] = 4 < dist[B] = 5 và dist[C] = inf). Không có đỉnh nào kề với E

Cài đặt thuật toán Dijkstra với Python

import heapq

def dijkstra(graph, start):
    # Khởi tạo dist ban đầu là vô cùng.
    dist = {node: float('infinity') for node in graph}
    # Đặt chi phí đi từ đỉnh start đến chính nó bằng 0.
    dist[start] = 0
    # Khởi tạo PriorityQueue và thêm start vào hàng đợi.
    pq = [(0, start)]
    while pq:
        # Lấy đỉnh có dist[u] nhỏ nhất từ hàng đợi.
        (cost, u) = heapq.heappop(pq)
        # Nếu đỉnh đã được duyệt rồi thì bỏ qua.
        if cost > dist[u]:
            continue
        # Duyệt qua các đỉnh v kề với u.
        for v, w in graph[u].items():
            # Tính chi phí đi từ u tới v.
            new_cost = dist[u] + w
            # Nếu chi phí mới nhỏ hơn chi phí đã biết, thì cập nhật.
            if new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(pq, (new_cost, v))
    return dist

# Ví dụ.
graph = {
    'A': {'B': 3, 'C': 4, 'D': 2},
    'B': {'A': 3, 'E': 1, 'F': 4},
    'C': {'A': 4, 'D': 1, 'G': 2},
    'D': {'A': 2, 'C': 1, 'G': 6},
    'E': {'B': 1, 'F': 2},
    'F': {'B': 4, 'E': 2, 'H': 3},
    'G': {'C': 2, 'D': 6, 'H': 1},
    'H': {'F': 3, 'G': 1},
}

print(dijkstra(graph, 'A'))

Với đồ thị đơn giản như trong ví dụ, khi chạy hàm dijkstra(graph, ‘A’), ta sẽ thu được kết quả là một dictionary với giá trị của mỗi đỉnh là chi phí đi ngắn nhất từ ‘A’ đến đỉnh đó, như sau:

{‘A’: 0, ‘B’: 3, ‘C’: 4, ‘D’: 2, ‘E’: 4, ‘F’: 5, ‘G’: 5, ‘H’: 6}

Điều này có nghĩa là để đi từ ‘A’ đến ‘B’, ta chỉ cần đi qua đỉnh ‘D’ với tổng chi phí là 2+1=3, còn để đi từ ‘A’ đến ‘H’, ta có thể đi qua đỉnh ‘C’, ‘G’ với tổng chi phí là 4+1=5.

Độ phức tạp của thuật toán

Độ phức tạp của thuật toán Dijkstra là O((V+E)logV), trong đó V là số lượng đỉnh của đồ thị và E là số lượng cạnh của đồ thị.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *