Floyd-Warshall algorithm: Difference between revisions
Content added Content deleted
Line 2,739: | Line 2,739: | ||
4 -> 2 -1.0 4 -> 2 |
4 -> 2 -1.0 4 -> 2 |
||
4 -> 3 1.0 4 -> 2 -> 1 -> 3</pre> |
4 -> 3 1.0 4 -> 2 -> 1 -> 3</pre> |
||
=={{header|OCaml}}== |
|||
{{trans|ATS}} |
|||
This implementation was written by referring frequently to [[#ATS|the ATS]], but differs from it considerably. For example, it assumes IEEE floating point, whereas the ATS purposely avoided that assumption. However, the "square matrix" type is very similar to the ATS equivalent. |
|||
<lang ocaml>(* |
|||
Floyd-Warshall algorithm. |
|||
See https://en.wikipedia.org/w/index.php?title=Floyd%E2%80%93Warshall_algorithm&oldid=1082310013 |
|||
*) |
|||
module Square_array = |
|||
(* Square arrays with 1-based indexing. *) |
|||
struct |
|||
type 'a t = |
|||
{ |
|||
n : int; |
|||
r : 'a Array.t |
|||
} |
|||
let make n fill = |
|||
let r = Array.make (n * n) fill in |
|||
{ n = n; r = r } |
|||
let get arr (i, j) = |
|||
Array.get arr.r ((i - 1) + (arr.n * (j - 1))) |
|||
let set arr (i, j) x = |
|||
Array.set arr.r ((i - 1) + (arr.n * (j - 1))) x |
|||
end |
|||
module Vertex = |
|||
(* A vertex is a positive integer, or 0 for the nil object. *) |
|||
struct |
|||
type t = int |
|||
let nil = 0 |
|||
let print_vertex u = |
|||
print_int u |
|||
let rec print_directed_list lst = |
|||
match lst with |
|||
| [] -> () |
|||
| [u] -> print_vertex u |
|||
| u :: tail -> |
|||
begin |
|||
print_vertex u; |
|||
print_string " -> "; |
|||
print_directed_list tail |
|||
end |
|||
end |
|||
module Edge = |
|||
(* A graph edge. *) |
|||
struct |
|||
type t = |
|||
{ |
|||
u : Vertex.t; |
|||
weight : Float.t; |
|||
v : Vertex.t |
|||
} |
|||
let make u weight v = |
|||
{ u = u; weight = weight; v = v } |
|||
end |
|||
module Paths = |
|||
(* The "next vertex" array and its operations. *) |
|||
struct |
|||
type t = Vertex.t Square_array.t |
|||
let make n = |
|||
Square_array.make n Vertex.nil |
|||
let get = Square_array.get |
|||
let set = Square_array.set |
|||
let path paths u v = |
|||
(* Path reconstruction. In the finest tradition of the standard |
|||
List module, this implementation is *not* tail recursive. *) |
|||
if Square_array.get paths (u, v) = Vertex.nil then |
|||
[] |
|||
else |
|||
let rec build_path paths u v = |
|||
if u = v then |
|||
[v] |
|||
else |
|||
let i = Square_array.get paths (u, v) in |
|||
u :: build_path paths i v |
|||
in |
|||
build_path paths u v |
|||
let print_path paths u v = |
|||
Vertex.print_directed_list (path paths u v) |
|||
end |
|||
module Distances = |
|||
(* The "distance" array and its operations. *) |
|||
struct |
|||
type t = Float.t Square_array.t |
|||
let make n = |
|||
Square_array.make n Float.infinity |
|||
let get = Square_array.get |
|||
let set = Square_array.set |
|||
end |
|||
let find_max_vertex edges = |
|||
(* This implementation is *not* tail recursive. *) |
|||
let rec find_max = |
|||
function |
|||
| [] -> Vertex.nil |
|||
| edge :: tail -> max (max Edge.(edge.u) Edge.(edge.v)) |
|||
(find_max tail) |
|||
in |
|||
find_max edges |
|||
let floyd_warshall edges = |
|||
(* This implementation assumes IEEE floating point. The OCaml Float |
|||
module explicitly specifies 64-bit IEEE floating point. *) |
|||
let _ = assert (edges <> []) in |
|||
let n = find_max_vertex edges in |
|||
let dist = Distances.make n in |
|||
let next = Paths.make n in |
|||
let rec read_edges = |
|||
function |
|||
| [] -> () |
|||
| edge :: tail -> |
|||
let u = Edge.(edge.u) in |
|||
let v = Edge.(edge.v) in |
|||
let weight = Edge.(edge.weight) in |
|||
begin |
|||
Distances.set dist (u, v) weight; |
|||
Paths.set next (u, v) v; |
|||
read_edges tail |
|||
end |
|||
in |
|||
begin |
|||
(* Initialization. *) |
|||
read_edges edges; |
|||
for i = 1 to n do |
|||
(* Distance from a vertex to itself = 0.0 *) |
|||
Distances.set dist (i, i) 0.0; |
|||
Paths.set next (i, i) i |
|||
done; |
|||
(* Perform the algorithm. *) |
|||
for k = 1 to n do |
|||
for i = 1 to n do |
|||
for j = 1 to n do |
|||
let dist_ij = Distances.get dist (i, j) in |
|||
let dist_ik = Distances.get dist (i, k) in |
|||
let dist_kj = Distances.get dist (k, j) in |
|||
let dist_ikj = dist_ik +. dist_kj in |
|||
if dist_ikj < dist_ij then |
|||
begin |
|||
Distances.set dist (i, j) dist_ikj; |
|||
Paths.set next (i, j) (Paths.get next (i, k)) |
|||
end |
|||
done |
|||
done |
|||
done; |
|||
(* Return the results, as a 3-tuple. *) |
|||
(n, dist, next) |
|||
end |
|||
let example_graph = |
|||
[Edge.make 1 (-2.0) 3; |
|||
Edge.make 3 (+2.0) 4; |
|||
Edge.make 4 (-1.0) 2; |
|||
Edge.make 2 (+4.0) 1; |
|||
Edge.make 2 (+3.0) 3] |
|||
;; |
|||
let (n, dist, next) = |
|||
floyd_warshall example_graph |
|||
;; |
|||
print_string " pair distance path"; |
|||
print_newline (); |
|||
print_string "---------------------------------------"; |
|||
print_newline (); |
|||
for u = 1 to n do |
|||
for v = 1 to n do |
|||
if u <> v then |
|||
begin |
|||
print_string " "; |
|||
Vertex.print_directed_list [u; v]; |
|||
print_string " "; |
|||
Printf.printf "%4.1f" (Distances.get dist (u, v)); |
|||
print_string " "; |
|||
Paths.print_path next u v; |
|||
print_newline () |
|||
end |
|||
done |
|||
done |
|||
;;</lang> |
|||
{{out}} |
|||
<pre>$ ocamlopt floyd_warshall_task.ml && ./a.out |
|||
pair distance path |
|||
--------------------------------------- |
|||
1 -> 2 -1.0 1 -> 3 -> 4 -> 2 |
|||
1 -> 3 -2.0 1 -> 3 |
|||
1 -> 4 0.0 1 -> 3 -> 4 |
|||
2 -> 1 4.0 2 -> 1 |
|||
2 -> 3 2.0 2 -> 1 -> 3 |
|||
2 -> 4 4.0 2 -> 1 -> 3 -> 4 |
|||
3 -> 1 5.0 3 -> 4 -> 2 -> 1 |
|||
3 -> 2 1.0 3 -> 4 -> 2 |
|||
3 -> 4 2.0 3 -> 4 |
|||
4 -> 1 3.0 4 -> 2 -> 1 |
|||
4 -> 2 -1.0 4 -> 2 |
|||
4 -> 3 1.0 4 -> 2 -> 1 -> 3</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |