THUẬT TOÁN 97
ĐƯỜNG ĐI NGẮN NHẤT
ROBERT W. FLOYD
Armour Research Foundation, Chicago, Ill.
procedure shortest path (m, n); value n; integer n; array m;
comment Initially m[i, j] is the length of a direct link from point i of a network to point j. If no direct link exists, m[i, j] is initially 1010. At completion, m[i, j] is the length of the shortest path from i to j. If none exists, m[i, j] is 1010. Reference: Warshall, S. A theorem on Boolean matrices. J.ACM 9(1962), 11-12;
begin
integer i, j, k; real inf, s; inf := 1010;
for i := 1 step 1 until n do
for j := 1 step 1 until n do
if m[j, i] < inf then
for k := 1 step 1 until n do
if m[i, k] < inf then
begin s := m[j, i] + m[i, k];
if s < m[j, k] then m[j, k] := s
end
end shortest path
Các đóng góp cho bộ phận này phải có dạng được nêu trong tuyên bố chính sách của Bộ phận Thuật toán (Communications, February, 1960), ngoại trừ việc phải sử dụng ký hiệu ALGOL 60 (xem Communications, May 1960). Các đóng góp phải được gửi thành hai bản cho J. H. Wegstein, Computation Laboratory, National Bureau of Standards, Washington 25, D. C. Các thuật toán phải ở dạng Reference của ALGOL 60 và được viết theo phong cách mô phỏng các thuật toán gần đây nhất xuất hiện trong bộ phận này.