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 từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị có trọng số không âm. Thuật toán này được đặt tên theo nhà toán học Edsger W. Dijkstra và được công bố lần đầu tiên vào năm 1959.

Bước đầu tiên

Thuật toán bắt đầu bằng cách chọn một đỉnh bất kỳ và đặt khoảng cách từ đỉnh đó đến tất cả các đỉnh khác bằng vô cùng, trừ khoảng cách từ đỉnh đó đến chính nó bằng 0.

Bước thứ hai

Sau đó, thuật toán duyệt qua tất cả các đỉnh của đồ thị, cập nhật khoảng cách từ đỉnh đang xét đến các đỉnh khác. Để cập nhật khoảng cách này, thuật toán sử dụng công thức:

new_distance = distance[current] + weight(current, neighbor)

Trong đó distance[current] là khoảng cách từ đỉnh bắt đầu đến đỉnh hiện tại đang xét, weight(current, neighbor) là trọng số của cạnh nối giữa đỉnh hiện tại đang xét và đỉnh kế tiếp, và new_distance là khoảng cách mới từ đỉnh bắt đầu đến đỉnh kế tiếp.

Bước cuối cùng

Cuối cùng, thuật toán chọn đỉnh có khoảng cách nhỏ nhất và đánh dấu nó đã được xét. Sau đó, thuật toán quay lại bước thứ hai và tiếp tục duyệt đến khi tất cả các đỉnh đều được đánh dấu đã xét hoặc khoảng cách từ đỉnh bắt đầu đến tất cả các đỉnh khác đã được cập nhật.

Dưới đây là đoạn mã Python mẫu cho thuật toán Dijkstra:

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    queue = [(0, start)]

    while queue:
        current_distance, current_vertex = heapq.heappop(queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances