-- Procedure Fig10_53 tests the all-pairs shortest paths algorithm with Ada.Text_IO, Ada.Integer_Text_IO; use Ada.Text_IO, Ada.Integer_Text_IO; procedure Fig10_53 is type Two_D_Array is array( Natural range <>, Natural range <> ) of Integer; A : Two_D_Array( 1..4, 1..4 ) := ( 1 => ( 0, 2, -2, 2 ), 2 => ( 1000, 0, -3, 1000 ), 3 => ( 4, 1000, 0, 1000 ), 4 => ( 1000, -2, 3, 0 ) ); D, Path: Two_D_Array( 1..4, 1..4 ); -- Compute all-shortest paths -- A contains the adjacency matrix with A( I, I ) presumed to be zero -- D contains the values of the shortest path -- A negative cycle exists iff D( i, i ) is set -- to a negative value at line 7 -- Actual path can be computed via another procedure using Path -- All indexes ranges for A and D are presumed to be identical procedure All_Pairs( A: Two_D_Array; D, Path : in out Two_D_Array ) is begin D := A; -- Initialize D and Path Path := ( others => ( others => 0 ) ); for K in D'range( 1 ) loop -- Consider each vertex as an intermediate for I in D'range( 1 ) loop for J in D'range( 1 ) loop if D( I, K ) + D( K, J ) < D( I, J ) then -- Update minimum path info D( I, J ) := D( I, K ) + D( K, J ); Path( I, J ) := K; end if; end loop; end loop; end loop; end All_Pairs; begin All_Pairs( A, D, Path ); for I in 1..4 loop for J in 1..4 loop Put( D( I, J ) ); end loop; New_Line; end loop; for I in 1..4 loop for J in 1..4 loop Put( Path( I, J ) ); end loop; New_Line; end loop; end Fig10_53;