Thuật toán Bellman-Ford

Thuật toán Bellman-Ford 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ố âm hoặc không. Thuật toán này được đặt tên theo nhà toán học Richard Bellman và Lester Ford Jr. và được công bố lần đầu tiên vào năm 1958.

Các bước của thuật toán

Thuật toán Bellman-Ford bắt đầu bằng cách đặt khoảng cách từ đỉnh bắt đầu đến tất cả các đỉnh khác bằng vô cùng, trừ khoảng cách từ đỉnh bắt đầu đến chính nó bằng 0. Sau đó, thuật toán duyệt qua tất cả các cạnh của đồ thị, cập nhật khoảng cách từ đỉnh bắt đầu đến các đỉnh khác. Cập nhật này được thực hiện bằng cách 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. Nếu khoảng cách mới này nhỏ hơn khoảng cách hiện tại, thuật toán sẽ cập nhật lại khoảng cách.

Thuật toán Bellman-Ford tiếp tục duyệt qua tất cả các cạnh của đồ thị, cập nhật khoảng cách đến khi không còn cập nhật được nữa hoặc đã cập nhật đến lần thứ N-1, với N là số lượng đỉnh của đồ thị. Nếu vẫn còn thể cập nhật được sau lần thứ N-1, tức là đồ thị có chu trình âm, điều này có nghĩa là không có đường đi ngắn nhất từ đỉnh bắt đầu đến các đỉnh khác.

Đoạn code Python mẫu

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

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

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                new_distance = distances[vertex] + weight
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance

    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distances[vertex] + weight < distances[neighbor]:
                raise ValueError("Graph contains negative weight cycle")

    return distances