Dijkstra Algorithm
Introduction
Dijkstra algorithm is a shortest path algorithm that is used to find the shortest path between two nodes in a graph. It was conceived by Edsger W. Dijkstra in 1956 and published three years later. The algorithm is used in various applications such as transportation networks, computer networks, and social networks.
Implementation
The Dijkstra algorithm is implemented in OCaml as follows:
let list_vertices graph =
List.fold_left (fun acc ((a, b), _) >
let acc = if List.mem b acc then acc else b::acc in
let acc = if List.mem a acc then acc else a::acc in
acc
) [] graph
let neighbors v =
List.fold_left (fun acc ((a, b), d) >
if a = v then (b, d)::acc else acc
) []
let remove_from v lst =
let rec aux acc = function [] > failwith "remove_from"
 x::xs > if x = v then List.rev_append acc xs else aux (x::acc) xs
in aux [] lst
let with_smallest_distance q dist =
match q with
 [] > assert false
 x::xs >
let rec aux distance v = function
 x::xs >
let d = Hashtbl.find dist x in
if d < distance
then aux d x xs
else aux distance v xs
 [] > (v, distance)
in
aux (Hashtbl.find dist x) x xs
let dijkstra max_val zero add graph source target =
let vertices = list_vertices graph in
let dist_between u v =
try List.assoc (u, v) graph
with _ > zero
in
let dist = Hashtbl.create 1 in
let previous = Hashtbl.create 1 in
List.iter (fun v > (* initializations *)
Hashtbl.add dist v max_val (* unknown distance function from source to v *)
) vertices;
Hashtbl.replace dist source zero; (* distance from source to source *)
let rec loop = function [] > ()
 q >
let u, dist_u =
with_smallest_distance q dist in (* vertex in q with smallest distance in dist *)
if dist_u = max_val then
failwith "vertices inaccessible"; (* all remaining vertices are inaccessible from source *)
if u = target then () else begin
let q = remove_from u q in
List.iter (fun (v, d) >
if List.mem v q then begin
let alt = add dist_u (dist_between u v) in
let dist_v = Hashtbl.find dist v in
if alt < dist_v then begin (* relax (u,v,a) *)
Hashtbl.replace dist v alt;
Hashtbl.replace previous v u; (* previous node in optimal path from source *)
end
end
) (neighbors u graph);
loop q
end
in
loop vertices;
let s = ref [] in
let u = ref target in
while Hashtbl.mem previous !u do
s := !u :: !s;
u := Hashtbl.find previous !u
done;
(source :: !s)
The function dijkstra
takes in a graph represented as a list of edges and their weights, a maximum value, a zero value, an addition function, a source node, and a target node. It returns a list of nodes representing the shortest path from the source to the target.
Here is how to call the function.
let () =
let graph =
[ ("a", "b"), 7;
("a", "c"), 9;
("a", "f"), 14;
("b", "c"), 10;
("b", "d"), 15;
("c", "d"), 11;
("c", "f"), 2;
("d", "e"), 6;
("e", "f"), 9; ]
in
let p = dijkstra max_int 0 (+) graph "a" "e" in
print_endline (String.concat " > " p)
Stepbystep Explanation

The function
list_vertices
takes in the graph and returns a list of all the vertices in the graph. It does this by iterating over each edge in the graph and adding its endpoints to the list of vertices if they are not already in it. 
The function
neighbors
takes in a vertexv
and returns a list of its neighbors and their distances. It does this by iterating over each edge in the graph and adding the neighbor ofv
and its distance to the list ifv
is the start point of the edge. 
The function
remove_from
takes in a vertexv
and a listlst
and returns a new list withv
removed from it. It does this by recursively iterating over the list and adding each element to a new list except forv
. 
The function
with_smallest_distance
takes in a list of verticesq
and a hash table of distancesdist
and returns the vertex inq
with the smallest distance indist
. It does this by recursively iterating over the list and comparing the distance of each vertex to the current smallest distance. 
The function
dijkstra
initializes the hash table of distancesdist
and the hash table of previous verticesprevious
. It then iterates over each vertex in the graph and adds it todist
with a distance ofmax_val
except for the source node, which is added with a distance ofzero
. It then enters a loop where it selects the vertex inq
with the smallest distance indist
usingwith_smallest_distance
. If the distance ismax_val
, it means all remaining vertices are inaccessible from the source, so it throws an error. If the selected vertex is the target node, it exits the loop. Otherwise, it removes the selected vertex fromq
and iterates over its neighbors. For each neighbor, it computes a new distancealt
from the source to the neighbor through the selected vertex and updatesdist
andprevious
ifalt
is smaller than the current distance indist
. It then continues the loop with the updatedq
. 
The function
dijkstra
ends by constructing the shortest path from the source to the target using the hash table of previous verticesprevious
. It starts at the target and iteratively adds the previous vertex to the path until it reaches the source.
Complexity Analysis
The time complexity of Dijkstraâ€™s algorithm is O((E+V)logV), where E is the number of edges and V is the number of vertices in the graph. This is because the algorithm iterates over each vertex once and each edge once, and it uses a priority queue to select the vertex with the smallest distance in each iteration, which takes logV time. The space complexity is O(V+E) because it stores the hash tables of distances and previous vertices, which have a size proportional to the number of vertices and edges in the graph.
In terms of the input parameters, the time complexity of list_vertices
is O(E), where E is the number of edges in the graph, because it iterates over each edge once. The time complexity of neighbors
is also O(E), because it iterates over each edge once. The time complexity of remove_from
is O(n), where n is the length of the input list, because it iterates over each element once. The time complexity of with_smallest_distance
is O(V), where V is the number of vertices in the input list, because it iterates over each vertex once. Therefore, the overall time complexity of the Dijkstra algorithm is dominated by the time complexity of the main loop, which is O((E+V)logV).
In terms of the space complexity, the hash tables used in the algorithm have a size proportional to the number of vertices in the graph, which is O(V). The priority queue used in with_smallest_distance
also has a size proportional to the number of vertices, which is O(V). Therefore, the overall space complexity of the algorithm is O(V+E).
Overall, the Dijkstra algorithm is an efficient algorithm for finding the shortest path between two nodes in a graph. Its time complexity is proportional to the number of edges and vertices in the graph, and its space complexity is proportional to the number of vertices.