Dijkstra’s algorithm is a graph traversal algorithm that finds the
shortest path between the source vertex and all other vertices in the graph.
data structure#
- Vertex: a struct that holds the vertex id.
- Edge: a struct that holds the vertex id of the start and end points,
and the cost of the edge which must be a positive integer.
- Graph: a struct that holds the vertices and edges.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| use std::cmp::Ordering;
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub struct Vertex {
// `id`: A unique identifier for the vertex, represented as a String.
id: String,
}
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Edge {
// `from`: The ID of the starting vertex of the edge.
from: String,
// `to`: The ID of the ending vertex of the edge.
to: String,
// `cost`: The weight or cost associated with traversing the edge.
cost: u32,
}
#[derive(Debug, PartialEq, Eq)]
pub struct Graph {
// `vertices`: A vector of `Vertex` structs, representing all vertices in the graph.
vertices: Vec<Vertex>,
// `edges`: A vector of `Edge` structs, representing all edges in the graph.
edges: Vec<Edge>,
}
#[derive(Clone, Eq, PartialEq)]
struct Node {
// `cost`: The current shortest distance from the source vertex to this vertex.
cost: u32,
// `vertex_id`: The ID of the vertex represented by this node.
vertex_id: String,
}
// Implement `Ord` trait for `Node` to make it usable in `BinaryHeap`.
impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
// Reverse the ordering of `cost` to make `BinaryHeap` behave as a min-heap.
// `BinaryHeap` in Rust is a max-heap by default, so flipping the comparison results
// in a min-heap behavior.
other.cost.cmp(&self.cost)
}
}
// Implement `PartialOrd` trait for `Node`.
impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
|
Dijkstra algorithm#
lowest cost#
- Initialize the distance from the source vertex to itself as 0.
- Push the source vertex into the priority queue with cost 0.
- Loop until the priority queue is empty.
- Pop the vertex with the smallest distance from the priority queue.
- If the current vertex is the destination, break the loop.
- If a shorter path to the current vertex has already been found, skip it.
- Iterate over all edges starting from the current vertex.
- Calculate the cost to the neighbor vertex through the current vertex.
- If a shorter path to the neighbor vertex is found, update the distance,
and push it into the priority queue.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| use std::collections::{BinaryHeap, HashMap};
impl Graph {
// Computes the lowest cost from src to dest using Dijkstra's algorithm.
pub fn dijkstra_cost(&self, src: &str, dest: &str) -> Option<u32> {
// `distances`: A `HashMap` to store the shortest distances from the source vertex to each vertex.
let mut distances: HashMap<String, u32> = HashMap::new();
// `pq`: A `BinaryHeap` (priority queue) to efficiently select the vertex with the smallest distance.
let mut pq: BinaryHeap<Node> = BinaryHeap::new();
// Initialize the distance from the source vertex to itself as 0.
distances.insert(src.to_string(), 0);
// Push the source vertex into the priority queue with cost 0.
pq.push(Node {
cost: 0,
vertex_id: src.to_string(),
});
// Loop until the priority queue is empty.
while let Some(Node { cost, vertex_id }) = pq.pop() {
// If the current vertex is the destination, return the cost.
if vertex_id == dest {
return Some(cost);
}
// If a shorter path to the current vertex has already been found, skip it.
if cost > *distances.get(&vertex_id).unwrap_or(&u32::MAX) {
continue;
}
// Iterate over all edges starting from the current vertex.
for edge in self.edges.iter().filter(|e| e.from == vertex_id) {
// Calculate the cost to the neighbor vertex through the current vertex.
let next_cost = cost + edge.cost;
// If a shorter path to the neighbor vertex is found, update the distance and push it into the priority queue.
if next_cost < *distances.get(&edge.to).unwrap_or(&u32::MAX) {
distances.insert(edge.to.clone(), next_cost);
pq.push(Node {
cost: next_cost,
vertex_id: edge.to.clone(),
});
}
}
}
// If no path is found, return None.
None
}
}
|
shortest path#
Much the same as the lowest cost, but keep a previous
HashMap
to
store the previous vertex in the shortest path to each vertex.
When a shorter path to a neighbor vertex is found, update
the distance and previous vertex, and push it into the priority queue.
When the destination is reached, reconstruct the path using
the previous HashMap backawards.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| impl Graph {
// Computes the shortest path from src to dest using Dijkstra's algorithm and returns the path as a vector of vertices.
pub fn dijkstra_path(&self, src: &str, dest: &str) -> Option<Vec<&Vertex>> {
// `distances`: A `HashMap` to store the shortest distances from the source vertex to each vertex.
let mut distances: HashMap<String, u32> = HashMap::new();
// `previous`: A `HashMap` to store the previous vertex in the shortest path to each vertex.
let mut previous: HashMap<String, String> = HashMap::new();
// `pq`: A `BinaryHeap` (priority queue) to efficiently select the vertex with the smallest distance.
let mut pq: BinaryHeap<Node> = BinaryHeap::new();
// Initialize the distance from the source vertex to itself as 0.
distances.insert(src.to_string(), 0);
// Push the source vertex into the priority queue with cost 0.
pq.push(Node {
cost: 0,
vertex_id: src.to_string(),
});
// Loop until the priority queue is empty.
while let Some(Node { cost, vertex_id }) = pq.pop() {
// If the current vertex is the destination, break the loop.
if vertex_id == dest {
break;
}
// If a shorter path to the current vertex has already been found, skip it.
if cost > *distances.get(&vertex_id).unwrap_or(&u32::MAX) {
continue;
}
// Iterate over all edges starting from the current vertex.
for edge in self.edges.iter().filter(|e| e.from == vertex_id) {
// Calculate the cost to the neighbor vertex through the current vertex.
let next_cost = cost + edge.cost;
// If a shorter path to the neighbor vertex is found, update the distance and previous vertex, and push it into the priority queue.
if next_cost < *distances.get(&edge.to).unwrap_or(&u32::MAX) {
distances.insert(edge.to.clone(), next_cost);
previous.insert(edge.to.clone(), vertex_id.clone());
pq.push(Node {
cost: next_cost,
vertex_id: edge.to.clone(),
});
}
}
}
// Construct the path from src to dest using the previous map.
self.construct_path(&previous, src, dest)
}
// Constructs the path from src to dest using the previous map.
fn construct_path(
&self,
previous: &HashMap<String, String>,
src: &str,
dest: &str,
) -> Option<Vec<&Vertex>> {
// `path`: A vector to store the vertices in the shortest path.
let mut path = Vec::new();
// `current`: The current vertex being processed, initialized with the destination.
let mut current = dest;
// Loop until the current vertex is the source vertex.
while current != src {
// Find the vertex in the graph by its ID.
if let Some(vertex) = self.vertices.iter().find(|v| v.id == current) {
// Add the vertex to the path.
path.push(vertex);
} else {
// If the vertex is not found, return None.
return None;
}
// Get the previous vertex from the previous map.
if let Some(prev) = previous.get(current) {
// Move to the previous vertex.
current = prev;
} else {
// If the previous vertex is not found, return None.
return None;
}
}
// Add the source vertex to the path.
if let Some(vertex) = self.vertices.iter().find(|v| v.id == src) {
path.push(vertex);
} else {
return None;
}
// Reverse the path to get the correct order.
path.reverse();
// Return the path.
Some(path)
}
}
|
time complexity and space complexity#
Time Complexity#
Adjacency List Representation with a Priority Queue (Binary Heap)#
Finding the Minimum Distance Vertex:
Using a binary heap, this step takes O(log V) time.
Updating Distances:
Each edge relaxation (updating a distance) takes O(log V) time due to
the heap update. In the worst case, we relax all edges, so this is O(E log V).
Overall: O((V + E) log V).
In a connected graph, E is at least V-1, so this simplifies to O(E log V).
This is the most common and efficient implementation for sparse graphs.
Adjacency List Representation with a Fibonacci Heap#
Finding the Minimum Distance Vertex: O(log V).
Updating Distances:
O(1) amortized time (meaning the average time per operation is constant).
Overall: O(V log V + E).
This is theoretically the fastest, but Fibonacci heaps
have a high constant overhead and are less commonly used in practice.
Key Considerations for Time Complexity#
Sparse vs. Dense Graphs:
For sparse graphs (E « V^2), O(E log V) is much better than O(V^2).
For dense graphs (E ≈ V^2), O(V^2) might be acceptable.
Priority Queue Implementation:
The choice of priority queue has a significant impact.
Binary heaps are the most common due to their balance of
performance and ease of implementation.
Space Complexity#
The space complexity of Dijkstra’s algorithm is primarily determined by
the data structures used to store the graph and the distances.
Adjacency Matrix:
O(V^2) to store the adjacency matrix.
O(V) to store the distances.
Overall: O(V^2).
Adjacency List:
O(V + E) to store the adjacency list (V for vertices, E for edges).
O(V) to store the distances.
O(V) to store the previous nodes for path reconstruction.
O(V) for the priority queue.
Overall: O(V + E).
Key Considerations for Space Complexity#
Adjacency lists are generally preferred for their lower space complexity,
especially for sparse graphs.
The distances and previous node maps will always be O(V).