アルゴリズム 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
この部門への投稿は、ALGOL 60の表記法を使用することを除き、Algorithms Department policy statement (Communications, February, 1960) に記載された形式でなければならない（Communications, May 1960を参照）。投稿は2部を J. H. Wegstein, Computation Laboratory, National Bureau of Standards, Washington 25, D. C. に送付する必要がある。アルゴリズムはALGOL 60のReference形式であり、この部門に掲載された直近のアルゴリズムを手本としたスタイルで記述されなければならない。