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

  1. Vertex: a struct that holds the vertex id.
  2. 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.
  3. 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

  1. Initialize the distance from the source vertex to itself as 0.
  2. Push the source vertex into the priority queue with cost 0.
  3. Loop until the priority queue is empty.
    1. Pop the vertex with the smallest distance from the priority queue.
    2. If the current vertex is the destination, break the loop.
    3. If a shorter path to the current vertex has already been found, skip it.
    4. Iterate over all edges starting from the current vertex.
    5. Calculate the cost to the neighbor vertex through the current vertex.
    6. 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)

  1. Finding the Minimum Distance Vertex: Using a binary heap, this step takes O(log V) time.

  2. 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).