Dijkstra’s Algorithm, also known as Dijkstra’s algorithm, is an algorithm used to solve the shortest path problem of weighted directed graphs or undirected graphs. This algorithm was invented by Dutch computer scientist Edsgel Dijkstra in 1956. It is an algorithm widely used in network routing and other fields.
In a 2001 interview, Dr. Dijkstra revealed the origins and process of designing this algorithm:
What is the shortest route from Rotterdam to Groningen? I spent about 20 minutes designing this algorithm to find the shortest path. One morning I was shopping in Amsterdam with my young fiancée. I felt a little tired, so we sat on the terrace of the cafe and drank a cup of coffee. I was wondering if I could solve this problem, and then I designed this shortest path algorithm. I said, this is a 20 minute design. In fact, it was not released until three years later in 1959, and one of the reasons it still looks so good now is that I didn’t have paper and pen when I was designing it, so I had to avoid all avoidable complexity. Ultimately, to my surprise, this algorithm became one of the cornerstones of my fame. –Quoted from the article“An interview with Edsger W. Dijkstra”.
1. Algorithm principle
The core idea of Dijkstra’s algorithm is to assume that the currently known shortest path from the starting point to a certain point is the shortest path that has been determined, and then gradually obtain the shortest path from the starting point to all other points by continuously expanding the known shortest path. .
Specifically, the algorithm is as follows:
Initialization algorithm
- Select a starting point s and initialize a distance array dist, where dist[i] represents the shortest distance from the starting point s to node i. Initially, all elements are set to positive infinity.
- Record a set S, which represents the set of nodes that have found the shortest path. Initially, S only contains the starting point s.
- For each node i, record a predecessor node prev[i], which represents the previous node of i on the shortest path from the starting point s to the node i. Initially, all elements are set to -1.
Loop solution
- Find the nearest node u that does not belong to set S from the distance array dist, and add it to set S.
- For all adjacent nodes v of node u, update their shortest distance and predecessor node:
- If the distance to v through u is smaller than the currently known shortest distance, dist[v] and prev[v] are updated.
- Otherwise, leave dist[v] and prev[v] unchanged.
- If the set S contains all nodes (that is, the shortest path from the starting point to all nodes has been found), the algorithm ends.
Output results
- The shortest path from the starting point to each node can be reconstructed based on the prev array.
2. Algorithm implementation
The following is a sample code of Dijkstra’s algorithm implemented in C++ language:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f; //define positive infinity
// Define the adjacency list representation of the graph
typedef pair<int, int> P; // first represents the node number, second represents the edge weight
vector<vector<p>> graph;
// Dijkstra's algorithm function
void dijkstra(int start, vector<int> & amp; dist, vector<int> & amp; prev) {
int n = graph.size();
dist.resize(n, INF);
prev.resize(n, -1);
dist[start] = 0;
prev[start] = start;
priority_queue<P, vector<p>, greater<p>> pq; // Small root heap, storing node numbers and distances
pq.push(make_pair(start, 0));
while (!pq.empty()) {
P p = pq.top();
pq.pop();
int u = p.first, d = p.second;
if (dist[u] < d) continue;
for (int i = 0; i < graph[u].size(); i + + ) {
int v = graph[u][i].first, w = graph[u][i].second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
prev[v] = u;
pq.push(make_pair(v, dist[v]));
}
}
}
}
// test code
int main() {
int n = 5; //Number of nodes
graph.resize(n);
//Initialize graph
graph[0].push_back(make_pair(1, 2));
graph[0].push_back(make_pair(2, 4));
graph[1].push_back(make_pair(2, 1));
graph[1].push_back(make_pair(3, 2));
graph[2].push_back(make_pair(3, 3));
graph[2].push_back(make_pair(4, 2));
graph[3].push_back(make_pair(4, 5));
// run algorithm
vector<int> dist, prev;
dijkstra(0, dist, prev);
//output result
for (int i = 0; i < n; i + + ) {
cout << "Node " << i << ": ";
if (dist[i] == INF) {
cout << "Unreachable" << endl;
} else {
cout << "Distance = " << dist[i] << ", Path = ";
int j = i;
while (prev[j] != j) {
cout << j << " <- ";
j = prev[j];
}
cout << j << endl;
}
}
return 0;
}
In the above code, we first define an adjacency list graph to represent the graph. Each element graph[i] is a vector array, representing the adjacent nodes of node i and the corresponding edge weights.
Then, we implemented the dijkstra() function to perform Dijkstra’s algorithm. This function accepts three parameters: the starting point start, and two output parameters dist and prev, which represent the shortest distance from the node to the starting point and the predecessor node respectively.
Inside the function, we first initialize the dist and prev arrays, setting all elements to positive infinity and -1 respectively. Then, we create a small root heap pq (implemented using priority_queue in STL) to store node numbers and distances. Add the starting point to the small root heap and set the distance to 0.
Next, we continuously take out the nearest node u from the small root heap, and update the shortest distance and predecessor node of all its adjacent nodes v. If the new distance is smaller than the currently known shortest distance, v is added to the small root heap and dist[v] and prev[v] are updated.
Finally, we output the shortest distance and path from each node to the starting point. If the node is unreachable, Unreachable is output. It should be noted that when reconstructing the path, we can use the prev array to search for the predecessor nodes one by one from the end point to build the complete path.
Suppose we have the following graph example, containing 6 nodes and the edges between them:
Node: 0 1 2 3 4 5 Edges: (0, 1, 4), (0, 2, 2), (1, 3, 2), (1, 2, 1), (2, 3, 5), (2, 4, 6), (3, 4, 1), (3, 5, 3), (4, 5, 4)
Now, we set the starting point to be node 0 and the end point to be node 5. Let us use Dijkstra’s algorithm to find the shortest path from start point 0 to end point 5.
First, we initialize the distance array dist and the predecessor array prev:
dist: [0, INF, INF, INF, INF, INF] prev: [-1, -1, -1, -1, -1, -1]
Then, we start from the starting point 0, add it to the set S, and update the shortest distance and predecessor nodes of the nodes adjacent to the starting point.
Iteration 1: The adjacent nodes of node 0 are node 1 and node 2, and their distances from the starting point 0 are 4 and 2 respectively. Since these two distances are smaller than the currently known distances, we update dist and prev:
dist: [0, 4, 2, INF, INF, INF] prev: [-1, 0, 0, -1, -1, -1]
Iteration 2: Next we need to select the node closest to the starting point 0, which is node 2 (distance is 2). Add node 2 to the set S, and update the shortest distance and predecessor nodes of nodes adjacent to node 2.
The adjacent nodes of node 2 are node 1, node 3 and node 4, and their distances from the starting point are 3, 7 and 8 respectively. Since the distance to node 1 is smaller than the currently known distance, we update dist and prev:
dist: [0, 3, 2, INF, INF, INF] prev: [-1, 2, 0, -1, -1, -1]
Iteration 3: Next, select the node closest to the starting point 0, which is node 1 (distance is 3). Add node 1 to the set S, and update the shortest distance and predecessor nodes of nodes adjacent to node 1.
The adjacent nodes of node 1 are node 3 and node 2, and their distances from the starting point are 5 and 4 respectively. Since the distance to node 3 is smaller than the currently known distance, we update dist and prev:
dist: [0, 3, 2, 5, INF, INF] prev: [-1, 2, 0, 1, -1, -1]
Iteration 4: Next, select the node closest to the starting point 0, which is node 3 (distance is 5). Add node 3 to the set S, and update the shortest distance and predecessor nodes of nodes adjacent to node 3.
The adjacent nodes of node 3 are node 4 and node 5, and their distances from the starting point are 6 and 8 respectively. Since the distance to node 4 is smaller than the currently known distance, we update dist and prev:
dist: [0, 3, 2, 5, 7, INF] prev: [-1, 2, 0, 1, 3, -1]
Iteration 5: Next, select the node closest to the starting point 0, which is node 4 (distance is 7). Add node 4 to the set S, and update the shortest distance and predecessor nodes of nodes adjacent to node 4.
The adjacent nodes of node 4 are node 3 and node 5, and their distances from the starting point are 6 and 11 respectively. Since the distance to node 3 is smaller than the currently known distance, we update dist and prev:
dist: [0, 3, 2, 5, 6, INF] prev: [-1, 2, 0, 1, 3, 4]
Iteration 6: The last node is end point 5, we add it to the set S and complete the algorithm.
At this time, the shortest path from starting point 0 to end point 5 is: 0 -> 2 -> 1 -> 3 -> 4 -> 5, and the total distance is 6.
This is the demonstration process of Dijkstra’s algorithm. By continuously updating the shortest distance and predecessor nodes, we can find the shortest path from the starting point to the ending point.
3. Algorithm optimization
Although Dijkstra’s algorithm has proven its efficiency and reliability in practice, it still leaves some room for optimization to further improve algorithm efficiency.
Heap optimization
The algorithm implementation we introduced above uses a small root heap to store node numbers and distance information. Doing this ensures that the node we take out every time is the closest to the starting point. However, when the number of nodes is large, the maintenance and adjustment costs of the heap will be very high, affecting the algorithm efficiency.
To address this problem, we can use a faster data structure to store node information. For example, we can use efficient heap implementations such as Fibonacci Heap or Binomial Heap to optimize the algorithm.
Parallel computing
Dijkstra’s algorithm is a graph-based algorithm, so its calculation can be distributed to improve computational efficiency.
For example, we can use distributed computing frameworks such as MapReduce to execute Dijkstra’s algorithm in parallel on multiple computing nodes and summarize the results at the end. In this way, we can significantly shorten the calculation time and improve the efficiency of the algorithm.
GPU-based optimization
Since Dijkstra’s algorithm involves a large amount of graph data processing and distance calculations, GPU (Graphics Processing Unit) can be used to accelerate the algorithm. By parallelizing the algorithm and dividing the graph across multiple GPU processing units, we can significantly improve algorithm efficiency.
4. Conclusion
Dijkstra’s algorithm is a classic algorithm for solving the shortest path problem in weighted directed or undirected graphs. This algorithm is based on a greedy strategy and gradually obtains the shortest path from the starting point to all other points by continuously expanding the known shortest path.
In practical applications, we often need to optimize algorithms to improve algorithm efficiency and performance. For example, we can use faster heap implementations, parallel computing, and GPU acceleration to further improve algorithm efficiency.
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56768 people are learning the system