Thuật toán Floyd-Warshall

Giới thiệu Thuật toán Floyd-Warshall

Thuật toán Floyd-Warshall là một thuật toán giải quyết bài toán tìm đường đi ngắn nhất (shortest path) giữa tất cả các cặp đỉnh trong đồ thị có hướng hoặc vô hướng, có thể có trọng số âm nhưng không chứa chu trình âm.

Ý tưởng của thuật toán là sử dụng phương pháp cập nhật giá trị của ma trận trọng số sao cho tại mỗi bước, ta sẽ xem xét một đỉnh mới và cập nhật giá trị ngắn nhất của đường đi giữa các cặp đỉnh thông qua đỉnh này. Cụ thể, ta sử dụng một ma trận kích thước VxV (V là số đỉnh của đồ thị) để lưu trữ giá trị ngắn nhất hiện tại giữa mỗi cặp đỉnh. Thuật toán sẽ thực hiện V lần lặp, mỗi lần lặp đều sẽ xem xét một đỉnh mới, và cập nhật giá trị ngắn nhất cho tất cả các cặp đỉnh thông qua đỉnh này.

Các bước thực hiện Thuật toán Floyd-Warshall

Các bước thực hiện thuật toán Floyd-Warshall như sau:

  1. Khởi tạo ma trận dist kích thước VxV, trong đó dist[i][j] là giá trị trọng số của cạnh từ đỉnh i đến đỉnh j. Nếu không có cạnh nào từ i đến j thì ta gán giá trị dist[i][j] = INF (vô cùng).

  2. Thực hiện V lần lặp, với mỗi lần lặp đánh giá tất cả các cặp đỉnh thông qua đỉnh hiện tại. Điều này có nghĩa là ta sẽ xem xét đỉnh k, và cập nhật giá trị ngắn nhất giữa tất cả các cặp đỉnh thông qua đỉnh k.

  3. Trong mỗi lần lặp, duyệt qua từng cặp đỉnh i, j. Nếu có đường đi từ i đến j thông qua đỉnh k, tức là dist[i][k] + dist[k][j] < dist[i][j], ta cập nhật giá trị của dist[i][j] bằng dist[i][k] + dist[k][j].

  4. Sau khi hoàn thành V lần lặp, ma trận dist sẽ lưu trữ giá trị ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị.

Với các bước trên, ta có thể thực hiện thuật toán Floyd-Warshall để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị.

Ví dụ Thuật toán Floyd-Warshall

Giả sử ta có đồ thị sau đây với 4 đỉnh và 5 cạnh:

    1
  /   \
 2     3
  \   /
    4

Ta có ma trận trọng số như sau:

     |  1  2  3  4
-----+------------
   1 |  0  3  8 INF
   2 |  3  0 INF  1
   3 |  8 INF  0  4
   4 | INF  1  4  0

Ta sẽ thực hiện thuật toán Floyd-Warshall để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.

Bước 1: Khởi tạo ma trận dist ban đầu:

     |  1  2  3  4
-----+------------
   1 |  0  3  8 INF
   2 |  3  0 INF  1
   3 |  8 INF  0  4
   4 | INF  1  4  0

Bước 2: Thực hiện lặp V lần, với mỗi lần lặp đánh giá tất cả các cặp đỉnh thông qua đỉnh hiện tại.

Với k = 1:

     |  1  2  3  4
-----+------------
   1 |  0  3  8 INF
   2 |  3  0 11   1
   3 |  8 11  0   4
   4 | INF  1  4   0

Với k = 2:

     |  1  2  3  4
-----+------------
   1 |  0  3  8  4
   2 |  3  0 11  1
   3 |  8 11  0  4
   4 |  4  1  4  0

Với k = 3:

     |  1  2  3  4
-----+------------
   1 |  0  3  8  4
   2 |  3  0  7  1
   3 |  8  7  0  4
   4 |  4  1  4  0

Bước 3: Ma trận dist sau khi thực hiện thuật toán là:

     |  1  2  3  4
-----+------------
   1 |  0  3  8  4
   2 |  3  0  7  1
   3 |  8  7  0  4
   4 |  4  1  4  0

Từ ma trận này, ta có thể thấy rằng đường đi ngắn nhất giữa các cặp đỉnh là:

  • (1,2): 3
  • (1,3): 8
  • (1,4): 4
  • (2,3): 7
  • (2,4): 1
  • (3,4): 4

Ma trận dist này cũng cho thấy rằng đường đi ngắn nhất giữa đỉnh 1 và đỉnh 4 là 4, và không tồn tại đường đi nào từ đỉnh 1 đến đỉnh 4 qua đỉnh 3 vì giá trị trọng số giữa 1 và 3 là INF.

Cài đặt thuật toán Floyd-Warshall

INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

Đầu vào của hàm floyd_warshall là ma trận trọng số của đồ thị. Đầu ra là ma trận dist chứa đường đi ngắn nhất giữa tất cả các cặp đỉnh.

Trong hàm floyd_warshall, ta bắt đầu bằng cách tạo ra một ma trận dist khởi tạo bằng ma trận trọng số của đồ thị ban đầu. Với mỗi giá trị dist[i][j], ta sẽ lưu trữ đường đi ngắn nhất từ đỉnh i đến đỉnh j.

Sau đó, ta thực hiện lặp V lần, với mỗi lần lặp đánh giá tất cả các cặp đỉnh thông qua đỉnh hiện tại. Để tìm đường đi ngắn nhất giữa hai đỉnh i và j thông qua đỉnh k, ta so sánh giá trị dist[i][j] hiện tại với giá trị dist[i][k] + dist[k][j]. Nếu giá trị dist[i][k] + dist[k][j] nhỏ hơn giá trị hiện tại của dist[i][j], ta cập nhật giá trị dist[i][j] bằng dist[i][k] + dist[k][j].

Cuối cùng, ta trả về ma trận dist chứa đường đi ngắn nhất giữa tất cả các cặp đỉnh.

Dưới đây là một đoạn code Python đầy đủ thực hiện thuật toán Floyd-Warshall để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị vô hướng có trọng số:

INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

# Example graph
graph = [
    [0, 3, 8, INF],
    [INF, 0, 7, 1],
    [INF, INF, 0, 4],
    [2, INF, INF, 0]
]

# Run the algorithm
dist = floyd_warshall(graph)

# Print the result
for row in dist:
    print(row)

Đầu vào của hàm floyd_warshall là một ma trận trọng số của đồ thị. Hàm trả về một ma trận dist chứa đường đi ngắn nhất giữa tất cả các cặp đỉnh. Chúng ta có thể chạy hàm này với một đồ thị bất kỳ để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của nó.

Trong ví dụ này, đầu ra sẽ là ma trận dist sau khi chạy thuật toán:

[0, 3, 8, 4]
[inf, 0, 7, 1]
[inf, inf, 0, 4]
[2, 5, 10, 0]

Ma trận này cho ta biết rằng đường đi ngắn nhất giữa các cặp đỉnh là:

  • (1,2): 3
  • (1,3): 8
  • (1,4): 4
  • (2,3): 7
  • (2,4): 1
  • (3,4): 4

Ta cũng có thể thấy rằng đường đi ngắn nhất giữa đỉnh 1 và đỉnh 4 là 4, và không tồn tại đường đi nào từ đỉnh 1 đến đỉnh 4 qua đỉnh 3 vì giá trị trọng số giữa 1 và 3 là inf.

Đánh giá độ phức tạp của thuật toán Floyd-Warshall

Độ phức tạp của thuật toán Floyd-Warshall là O(n^3), với n là số đỉnh của đồ thị. Cụ thể, với mỗi đỉnh k, thuật toán cập nhật lại khoảng cách nhỏ nhất giữa mỗi cặp đỉnh i và j bằng cách so sánh khoảng cách giữa i và j với tổng khoảng cách giữa i và k cộng với khoảng cách giữa k và j. Vì vậy, thuật toán sẽ phải thực hiện O(n^3) lần so sánh để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.

Tuy nhiên, trong trường hợp đồ thị có độ dày thấp, tức là số cạnh của đồ thị là O(n), thì độ phức tạp của thuật toán sẽ được giảm xuống còn O(n^2). Điều này do trong trường hợp đồ thị có độ dày thấp, ma trận trọng số chỉ có một số lượng hữu hạn các giá trị khác vô cùng (INF), và số lượng các giá trị khác vô cùng này cũng sẽ tương đối nhỏ, vì vậy số lần lặp lại của vòng lặp cũng giảm xuống.

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 *