ALGORITHM 97
最短路径
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
本部门的投稿必须采用《算法部门政策声明》（Communications，1960年2月）中规定的形式，但应使用ALGOL 60表示法（参见Communications，1960年5月）。投稿应一式两份寄送至J. H. Wegstein，Computation Laboratory，National Bureau of Standards，Washington 25, D. C.。算法应采用ALGOL 60的Reference形式，并以本部门最近发表的算法所采用的风格撰写。