Thuật toán Floyd-Warshall

Thuật toán Floyd-Warshall là một thuật toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có trọng số. Thuật toán này được đặt tên theo các nhà toán học Robert Floyd và Stephen Warshall, và được công bố lần đầu tiên vào năm 1962.

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

Thuật toán Floyd-Warshall bắt đầu bằng cách khởi tạo ma trận khoảng cách ban đầu. Ma trận này có kích thước bằng số lượng đỉnh trong đồ thị, và khoảng cách ban đầu từ một đỉnh đến một đỉnh khác được lưu trong ma trận này.

Sau đó, thuật toán duyệt qua tất cả các cặp đỉnh trong đồ thị và cập nhật khoảng cách giữa chúng nếu có đường đi ngắn hơn. Cập nhật khoảng cách này được thực hiện bằng cách sử dụng công thức:

new_distance = distance[i][k] + distance[k][j]

Trong đó distance[i][k] là khoảng cách hiện tại từ đỉnh i đến đỉnh k, distance[k][j] là khoảng cách hiện tại từ đỉnh k đến đỉnh j, và new_distance là khoảng cách mới từ đỉnh i đến đỉnh j.

Đoạn code Python mẫu

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

def floyd_warshall(graph):
    distance = [[float('inf') if i != j else 0 for j in range(len(graph))] for i in range(len(graph))]

    for i in range(len(graph)):
        for j in graph[i]:
            distance[i][j] = graph[i][j]

    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

    return distance

Các tham số

Thuật toán Floyd-Warshall cần một tham số duy nhất là đồ thị có trọng số. Đồ thị này có thể được biểu diễn dưới dạng một danh sách kề, trong đó mỗi cặp đỉnh được nối với nhau bởi một cạnh có trọng số tương ứng.

Hy vọng thông tin này sẽ giúp bạn hiểu rõ hơn về thuật toán Floyd-Warshall và cách sử dụng nó trong các ứng dụng thực tế.