Floyd-Warshall algorithm: Difference between revisions

=={{header|Ada}}==

{{trans|Scheme}}

<lang ada>--

-- Floyd-Warshall algorithm.

--

-- See https://en.wikipedia.org/w/index.php?title=Floyd%E2%80%93Warshall_algorithm&oldid=1082310013

--

with Ada.Containers.Vectors;

with Ada.Text_IO; use Ada.Text_IO;

with Interfaces; use Interfaces;

with Ada.Numerics.Generic_Elementary_Functions;

procedure floyd_warshall_task

is

Floyd_Warshall_Exception : exception;

-- The floating point type we shall use is one that has infinities.

subtype FloatPt is IEEE_Float_32;

package FloatPt_Elementary_Functions is new Ada.Numerics

.Generic_Elementary_Functions

(FloatPt);

use FloatPt_Elementary_Functions;

-- The following should overflow and give us an IEEE infinity. But I

-- have kept the code so you could use some non-IEEE floating point

-- format and set ENORMOUS_FloatPt to some value that is finite but

-- much larger than actual graph traversal distances.

ENORMOUS_FloatPt : constant FloatPt :=

(FloatPt (1.0) / FloatPt (1.0e-37))**1.0e37;

package FloatPt_IO is new Float_IO (FloatPt);

use FloatPt_IO;

--

-- Input is a Vector of records representing the edges of a graph.

--

-- Vertices are identified by integers from 1 .. n.

--

type edge is record

u : Positive;

weight : FloatPt;

v : Positive;

end record;

package Edge_Vectors is new Ada.Containers.Vectors

(Index_Type => Positive, Element_Type => edge);

use Edge_Vectors;

subtype edge_vector is Edge_Vectors.Vector;

--

-- Floyd-Warshall.

--

type distance_array is

array (Positive range <>, Positive range <>) of FloatPt;

type next_vertex_array is

array (Positive range <>, Positive range <>) of Natural;

Nil_Vertex : constant Natural := 0;

function find_max_vertex -- Find the maximum vertex number.

(edges : in edge_vector)

return Positive

is

max_vertex : Positive;

begin

if Is_Empty (edges) then

raise Floyd_Warshall_Exception with "no edges";

end if;

max_vertex := 1;

for i in edges.First_Index .. edges.Last_Index loop

max_vertex := Positive'Max (max_vertex, edges.Element (i).u);

max_vertex := Positive'Max (max_vertex, edges.Element (i).v);

end loop;

return max_vertex;

end find_max_vertex;

procedure floyd_warshall -- Perform Floyd-Warshall.

(edges : in edge_vector;

max_vertex : in Positive;

distance : out distance_array;

next_vertex : out next_vertex_array)

is

u, v : Positive;

dist_ikj : FloatPt;

begin

-- Initialize.

for i in 1 .. max_vertex loop

for j in 1 .. max_vertex loop

distance (i, j) := ENORMOUS_FloatPt;

next_vertex (i, j) := Nil_Vertex;

end loop;

end loop;

for i in edges.First_Index .. edges.Last_Index loop

u := edges.Element (i).u;

v := edges.Element (i).v;

distance (u, v) := edges.Element (i).weight;

next_vertex (u, v) := v;

end loop;

for i in 1 .. max_vertex loop

distance (i, i) :=

FloatPt (0.0); -- Distance from a vertex to itself.

next_vertex (i, i) := i;

end loop;

-- Perform the algorithm.

for k in 1 .. max_vertex loop

for i in 1 .. max_vertex loop

for j in 1 .. max_vertex loop

dist_ikj := distance (i, k) + distance (k, j);

if dist_ikj < distance (i, j) then

distance (i, j) := dist_ikj;

next_vertex (i, j) := next_vertex (i, k);

end if;

end loop;

end loop;

end loop;

end floyd_warshall;

--

-- Path reconstruction.

--

procedure put_path

(next_vertex : in next_vertex_array;

u, v : in Positive)

is

i : Positive;

begin

if next_vertex (u, v) /= Nil_Vertex then

i := u;

Put (Positive'Image (i));

while i /= v loop

Put (" ->");

i := next_vertex (i, v);

Put (Positive'Image (i));

end loop;

end if;

end put_path;

example_graph : edge_vector;

max_vertex : Positive;

begin

Append (example_graph, (u => 1, weight => FloatPt (-2.0), v => 3));

Append (example_graph, (u => 3, weight => FloatPt (+2.0), v => 4));

Append (example_graph, (u => 4, weight => FloatPt (-1.0), v => 2));

Append (example_graph, (u => 2, weight => FloatPt (+4.0), v => 1));

Append (example_graph, (u => 2, weight => FloatPt (+3.0), v => 3));

max_vertex := find_max_vertex (example_graph);

declare

distance : distance_array (1 .. max_vertex, 1 .. max_vertex);

next_vertex : next_vertex_array

(1 .. max_vertex, 1 .. max_vertex);

begin

floyd_warshall (example_graph, max_vertex, distance, next_vertex);

Put_Line (" pair distance path");

Put_Line ("---------------------------------------------");

for u in 1 .. max_vertex loop

for v in 1 .. max_vertex loop

if u /= v then

Put (Positive'Image (u));

Put (" ->");

Put (Positive'Image (v));

Put (" ");

Put (FloatPt'Image (distance (u, v)));

Put (" ");

put_path (next_vertex, u, v);

Put_Line ("");

end if;

end loop;

end loop;

end;

end floyd_warshall_task;</lang>

{{out}}

<pre>$ gnatmake -q floyd_warshall_task.adb && ./floyd_warshall_task

pair distance path

---------------------------------------------

1 -> 2 -1.00000E+00 1 -> 3 -> 4 -> 2

1 -> 3 -2.00000E+00 1 -> 3

1 -> 4 0.00000E+00 1 -> 3 -> 4

2 -> 1 4.00000E+00 2 -> 1

2 -> 3 2.00000E+00 2 -> 1 -> 3

2 -> 4 4.00000E+00 2 -> 1 -> 3 -> 4

3 -> 1 5.00000E+00 3 -> 4 -> 2 -> 1

3 -> 2 1.00000E+00 3 -> 4 -> 2

3 -> 4 2.00000E+00 3 -> 4

4 -> 1 3.00000E+00 4 -> 2 -> 1

4 -> 2 -1.00000E+00 4 -> 2

4 -> 3 1.00000E+00 4 -> 2 -> 1 -> 3</pre>