Floyd-Warshall algorithm: Difference between revisions
→{{header|C}}
Line 165:
4 -> 3 1
</pre>
=={{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>
=={{header|C}}==
| |||