Trong hướng dẫn này, bạn sẽ tìm hiểu cách hoạt động của thuật toán floyd-warhall. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của thuật toán floyd-warhall trong C, C ++, Java và Python.
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 một đồ thị có trọng số. Thuật toán này hoạt động cho cả đồ thị có trọng số có hướng và vô hướng. Tuy nhiên, nó không hoạt động đối với các đồ thị có chu kỳ âm (trong đó tổng các cạnh trong một chu kỳ là âm).
Đồ thị có trọng số là đồ thị trong đó mỗi cạnh có một giá trị số được liên kết với nó.
Thuật toán Floyd-Warhshall còn được gọi là thuật toán Floyd, thuật toán Roy-Floyd, thuật toán Roy-Warshall, hoặc thuật toán WFI.
Thuật toán này tuân theo phương pháp lập trình động để tìm các đường đi ngắn nhất.
Thuật toán Floyd-Warshall hoạt động như thế nào?
Cho đồ thị đã cho là:
Đồ thị ban đầu
Làm theo các bước dưới đây để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.
- Tạo một ma trận có kích thước với n là số đỉnh. Hàng và cột được lập chỉ mục lần lượt là i và j. i và j là các đỉnh của đồ thị. Mỗi ô A (i) (j) được điền khoảng cách từ đỉnh đến đỉnh. Nếu không có đường đi từ đỉnh đến đỉnh, ô được để là vô cùng. Điền vào mỗi ô với khoảng cách giữa đỉnh thứ i và thứ j
A0n*nithjthithjth
- Bây giờ, hãy tạo một ma trận bằng cách sử dụng ma trận . Các phần tử trong cột đầu tiên và hàng đầu tiên được giữ nguyên. Các ô còn lại được điền theo cách sau. Gọi k là đỉnh trung gian trên đường đi ngắn nhất từ nguồn đến đích. Trong bước này, k là đỉnh đầu tiên. được lấp đầy với . Tức là, nếu khoảng cách trực tiếp từ nguồn đến đích lớn hơn đường đi qua đỉnh k, thì ô được lấp đầy bởi . Trong bước này, k là đỉnh 1. Ta tính khoảng cách từ đỉnh nguồn đến đỉnh đích thông qua đỉnh k này. Tính khoảng cách từ đỉnh nguồn đến đỉnh đích qua đỉnh k Ví dụ: Cho
A1A0A(i)(j)(A(i)(k) + A(k)(j)) if (A(i)(j)> A(i)(k) + A(k)(j))A(i)(k) + A(k)(j)
A1(2, 4), khoảng cách trực tiếp từ đỉnh 2 đến 4 là 4 và tổng khoảng cách từ đỉnh 2 đến 4 qua đỉnh (tức là từ đỉnh 2 đến 1 và từ đỉnh 1 đến 4) là 7. Vì4 < 7, được điền bằng 4.A0(2, 4) - Tương tự, được tạo bằng cách sử dụng . Các phần tử trong cột thứ hai và hàng thứ hai được giữ nguyên. Trong bước này, k là đỉnh thứ hai (tức là đỉnh 2). Các bước còn lại tương tự như bước 2 . Tính khoảng cách từ đỉnh nguồn đến đỉnh đích qua đỉnh 2 này
A2A3
- Tương tự, và cũng được tạo. Tính khoảng cách từ đỉnh nguồn đến đỉnh đích qua đỉnh này 3 Tính khoảng cách từ đỉnh nguồn đến đỉnh đích qua đỉnh này 4
A3A4
A4đưa ra đường đi ngắn nhất giữa mỗi cặp đỉnh.
Thuật toán Floyd-Warshall
n = không có đỉnh A = ma trận có chiều n * n với k = 1 đến n với i = 1 đến n với j = 1 đến n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) trả về A
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # Floyd Warshall Algorithm in python # The number of vertices nV = 4 INF = 999 # Algorithm implementation def floyd_warshall(G): distance = list(map(lambda i: list(map(lambda j: j, i)), G)) # Adding vertices individually for k in range(nV): for i in range(nV): for j in range(nV): distance(i)(j) = min(distance(i)(j), distance(i)(k) + distance(k)(j)) print_solution(distance) # Printing the solution def print_solution(distance): for i in range(nV): for j in range(nV): if(distance(i)(j) == INF): print("INF", end=" ") else: print(distance(i)(j), end=" ") print(" ") G = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)) floyd_warshall(G)
// Floyd Warshall Algorithm in Java class FloydWarshall ( final static int INF = 9999, nV = 4; // Implementing floyd warshall algorithm void floydWarshall(int graph()()) ( int matrix()() = new int(nV)(nV); int i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()()) ( for (int i = 0; i < nV; ++i) ( for (int j = 0; j < nV; ++j) ( if (matrix(i)(j) == INF) System.out.print("INF "); else System.out.print(matrix(i)(j) + " "); ) System.out.println(); ) ) public static void main(String() args) ( int graph()() = ( ( 0, 3, INF, 5 ), ( 2, 0, INF, 4 ), ( INF, 1, 0, INF ), ( INF, INF, 2, 0 ) ); FloydWarshall a = new FloydWarshall(); a.floydWarshall(graph); ) )
// Floyd-Warshall Algorithm in C #include // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )
// Floyd-Warshall Algorithm in C++ #include using namespace std; // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )
Độ phức tạp của thuật toán Floyd Warshall
Thời gian phức tạp
Có ba vòng lặp. Mỗi vòng lặp có độ phức tạp không đổi. Vì vậy, độ phức tạp về thời gian của thuật toán Floyd-Warshall là .O(n3)
Không gian phức tạp
Độ phức tạp không gian của thuật toán Floyd-Warshall là .O(n2)
Ứng dụng thuật toán Floyd Warshall
- Để tìm đường đi ngắn nhất là đồ thị có hướng
- Để tìm cách đóng theo hướng bắc cầu của đồ thị có hướng
- Để tìm Nghịch đảo của ma trận thực
- Để kiểm tra xem một biểu đồ vô hướng có phải là lưỡng phân hay không
