Thuật toán Floyd–Warshall

Trong khoa học máy tính, thuật toán Floyd-Warshall (còn được gọi là thuật toán Floyd, thuật toán Roy-Warshall, thuật toán Roy-Floyd hoặc thuật toán WFI) là một thuật toán để tìm đường đi ngắn nhất trong đồ thị có hướng đồ thị có trọng số với trọng số cạnh dương hoặc âm (nhưng không có chu trình âm).^[1][2] Một lần thực hiện thuật toán sẽ tìm ra độ dài (trọng số tổng hợp) của đường đi ngắn nhất giữa mọi cặp đỉnh. Mặc dù nó không trả về chi tiết của các đường đi, có thể khôi phục các đường đi với sửa đổi đơn giản cho thuật toán. Các phiên bản của thuật toán cũng có thể được sử dụng để tìm bao đóng chuyển tiếp của quan hệ ${\displaystyle R}$, hoặc (liên quan đến phương pháp bỏ phiếu Schulze) đường đi rộng nhất giữa mọi cặp đỉnh trong đồ thị có trọng số.

Lịch sử và tên gọi

Thuật toán Floyd–Warshall là một ví dụ về quy hoạch động, và được xuất bản dưới dạng hiện nay của nó bởi Robert Floyd vào năm 1962.^[3] Tuy nhiên, nó về cơ bản giống như các thuật toán trước đó được xuất bản bởi Bernard Roy vào năm 1959^[4] và cũng bởi Stephen Warshall vào năm 1962^[5] để tìm bao đóng chuyển tiếp của một đồ thị,^[6] và có liên quan chặt chẽ với thuật toán của Kleene (xuất bản vào năm 1956) để chuyển đổi một tự động hóa hữu hạn xác định thành một biểu thức chính quy.^[7] Định dạng hiện đại của thuật toán dưới dạng ba vòng lặp lồng nhau được mô tả đầu tiên bởi Peter Ingerman, cũng vào năm 1962.^[8]

Thuật toán

Thuật toán Floyd–Warshall so sánh nhiều đường đi khả dĩ trong đồ thị giữa mỗi cặp đỉnh. Nó được đảm bảo để tìm tất cả các đường đi ngắn nhất và có thể làm điều này với ${\displaystyle \Theta (|V|^{3})}$ so sánh trong một đồ thị, mặc dù có thể có ${\displaystyle \Theta (|V|^{2})}$ cạnh trong đồ thị. Nó làm như vậy bằng cách tăng dần ước tính đường đi ngắn nhất giữa hai đỉnh, cho đến khi ước tính tối ưu.

Xét đồ thị ${\displaystyle G}$ với đỉnh ${\displaystyle V}$ đánh số từ 1 đến ${\displaystyle N}$. Hãy xem xét hàm ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ trả về độ dài của đường đi ngắn nhất (nếu tồn tại) từ ${\displaystyle i}$ đến ${\displaystyle j}$ sử dụng các đỉnh chỉ từ tập ${\displaystyle \{1,2,\ldots ,k\}}$ làm điểm trung gian trong đường đi. Giờ đây, với hàm này, mục tiêu của chúng ta là tìm độ dài của đường đi ngắn nhất từ mỗi ${\displaystyle i}$ đến từng ${\displaystyle j}$ sử dụng bất kỳ đỉnh nào trong ${\displaystyle \{1,2,\ldots ,N\}}$. Theo định nghĩa, đây là giá trị ${\displaystyle \mathrm {shortestPath} (i,j,N)}$, mà chúng ta sẽ tìm đệ quy.

Chú ý rằng ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ phải nhỏ hơn hoặc bằng ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$: sẽ linh hoạt hơn nếu được phép sử dụng đỉnh ${\displaystyle k}$. Nếu ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ thực sự nhỏ hơn ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$, thì phải có một đường đi từ ${\displaystyle i}$ đến ${\displaystyle j}$ sử dụng các đỉnh ${\displaystyle \{1,2,\ldots ,k\}}$ mà ngắn hơn bất kỳ đường đi nào không sử dụng đỉnh ${\displaystyle k}$. Đường đi này có thể được phân rã thành:

(1) một đường đi từ ${\displaystyle i}$ đến ${\displaystyle k}$ sử dụng các đỉnh ${\displaystyle \{1,2,\ldots ,k-1\}}$, kế tiếp là

(2) một đường đi từ ${\displaystyle k}$ đến ${\displaystyle j}$ sử dụng các đỉnh ${\displaystyle \{1,2,\ldots ,k-1\}}$.

Và dĩ nhiên, chúng phải là các đường đi ngắn nhất như vậy, nếu không chúng ta có thể làm giảm độ dài hơn nữa. Nói cách khác, chúng ta đã đến công thức đệ quy:

${\displaystyle \mathrm {shortestPath} (i,j,k)=}$

${\displaystyle \mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),}$

${\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}}$.

Trong khi đó, trường hợp cơ sở được đưa ra bởi

${\displaystyle \mathrm {shortestPath} (i,j,0)=w(i,j),}$

ở đó ${\displaystyle w(i,j)}$ biểu thị trọng số của cạnh từ ${\displaystyle i}$ đến ${\displaystyle j}$ nếu tồn tại và ∞ (vô cùng) trong trường hợp khác.

Các công thức này là trọng tâm của thuật toán Floyd-Warshall. Thuật toán hoạt động bằng cách tính ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ cho tất cả các cặp ${\displaystyle (i,j)}$ với ${\displaystyle k=0}$, sau đó là ${\displaystyle k=1}$, sau đó là ${\displaystyle k=2}$, vân vân. Quá trình này tiếp tục cho đến khi ${\displaystyle k=N}$, và chúng ta đã tìm thấy đường đi ngắn nhất cho tất cả các cặp ${\displaystyle (i,j)}$ sử dụng bất kỳ đỉnh trung gian nào. Mã giả cho phiên bản cơ bản này là:

Mã giả

cho dist là một mảng |V| × |V| của khoảng cách tối thiểu khởi tạo thành ∞ (vô cùng)
đối với mỗi cạnh (u, v) thực hiện
    dist[u][v] ← w(u, v)  // Trọng số của cạnh (u, v)
đối với mỗi đỉnh v thực hiện
    dist[v][v] ← 0
đối với k từ 1 đến |V|
    đối với i từ 1 đến |V|
        đối với j từ 1 đến |V|
            nếu dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            kết thúc nếu

Ví dụ

Thuật toán trên được thực hiện trên đồ thị ở bên trái trong hình dưới đây:

Trước lần duyệt đệ quy đầu tiên của vòng lặp ngoài, gán k = 0 ở trên, các đường đi được biết chỉ tương ứng với các cạnh đơn trong đồ thị. Tại k = 1, đường đi đi qua đỉnh 1 được tìm thấy: cụ thể là đường đi [2,1,3] được tìm thấy, thay thế đường đi [2,3] có ít cạnh hơn nhưng lại dài hơn (về trọng số). Tại k = 2, đường đi đi qua các đỉnh {1,2} được tìm thấy. Các ô màu đỏ và xanh dương cho thấy cách mà đường đi [4,2,1,3] được ghép từ hai đường đi đã biết [4,2] và [2,1,3] gặp trong các lần lặp trước, với 2 trong giao điểm. Đường đi [4,2,3] không được xem xét, vì [2,1,3] là đường đi ngắn nhất gặp từ 2 đến 3. Tại k = 3, đường đi qua các đỉnh {1,2,3} được tìm thấy. Cuối cùng, tại k = 4, tất cả các đường đi ngắn nhất được tìm thấy.

Ma trận khoảng cách ở mỗi lần lặp của k, với các khoảng cách được cập nhật được in đậm, sẽ là:

k = 0		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 1		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 2		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0

k = 3		j
		1	2	3	4
i	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0

k = 4		j
		1	2	3	4
i	1	0	−1	−2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	−1	1	0

So sánh giữa 2 thuật toán dijkstra và Floyd-Warshall

Thuật toán Dijkstra bình thường có 2 vòng lặp lồng nhau sẽ có Độ phức tạp thuật toán là ${\displaystyle O(n^{2})}$. Thuật toán Floyd–Warshall bình thường có 3 vòng lặp lồng nhau sẽ có Độ phức tạp thuật toán là ${\displaystyle O(n^{3})}$.

	Dijsktra	Floyd-Warshall
Ưu điểm	Chi phí thấp hơn Thuật toán Floyd–Warshall	Không cần chạy lại Thuật toán (có nghĩa là có tính kế thừa từ đường đi lẫn nhau) Có thể chạy được với trọng số âm.
Nhược điểm	Không chạy được với trọng số âm.	Chi phí cao ${\displaystyle O(n^{3})}$ cho mỗi cặp đỉnh

Chú thích

1. Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford (1994). Introduction to algorithms. MIT press Cambridge, MA, USA.
2. Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5th Edition. Addison Wesley. ISBN 978-0-07-119881-3.
3. Floyd, Robert W. (tháng 6 năm 1962). “Algorithm 97: Shortest Path”. Communications of the ACM. 5 (6): 345. doi:10.1145/367766.368168. S2CID 2003382.
4. Roy, Bernard (1959). “Transitivité et connexité”. C. R. Acad. Sci. Paris (bằng tiếng Pháp). 249: 216–218.
5. Warshall, Stephen (tháng 1 năm 1962). “A theorem on Boolean matrices”. Journal of the ACM. 9 (1): 11–12. doi:10.1145/321105.321107. S2CID 33763989.
6. Weisstein, Eric W., "Thuật toán Floyd-Warshall", MathWorld.
7. Kleene, S. C. (1956). “Representation of events in nerve nets and finite automata”. Trong C. E. Shannon và J. McCarthy (biên tập). Automata Studies. Princeton University Press. tr. 3–42.
8. Ingerman, Peter Z. (tháng 11 năm 1962). “Algorithm 141: Path Matrix”. Communications of the ACM. 5 (11): 556. doi:10.1145/368996.369016. S2CID 29010500.