1677155
Thuật toán Floyd–Warshall
https://vi.wikipedia.org/wiki?curid=1677155
Title: Thuật toán Floyd–Warshall
Xét đồ thị formula_4 với đỉnh formula_5 đánh số từ 1 đến formula_6. Hãy xem xét hàm formula_7 trả về độ dài của đường đi ngắn nhất (nếu tồn tại) từ formula_8 đến formula_9 sử dụng các đỉnh chỉ từ tập formula_10 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 formula_8 đến từng formula_9 sử dụng bất kỳ đỉnh nào trong formula_13. Theo định nghĩa, đây là giá trị formula_14, mà chúng ta sẽ tìm đệ quy.
Chú ý rằng formula_7 phải nhỏ hơn hoặc bằng formula_16: sẽ linh hoạt hơn nếu được phép sử dụng đỉnh formula_17. Nếu formula_7 thực sự nhỏ hơn formula_16, thì phải có một đường đi từ formula_8 đến formula_9 sử dụng các đỉnh formula_10 mà ngắn hơn bất kỳ đường đi nào không sử dụng đỉnh formula_17. Đường đi này có thể được phân rã thành:
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:
Trong khi đó, trường hợp cơ sở được đưa ra bởi
ở đó formula_34 biểu thị trọng số của cạnh từ formula_8 đến formula_9 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 formula_7 cho tất cả các cặp formula_38 với formula_39, sau đó là formula_40, sau đó là formula_41, vân vân. Quá trình này tiếp tục cho đến khi formula_42, và chúng ta đã tìm thấy đường đi ngắn nhất cho tất cả các cặp formula_38 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