Last Updated on September 22, 2023 by Prepbytes
Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm works by maintaining a set of vertices that have already been visited, and a set of vertices that have not yet been visited. Let us discuss Dijkstra algorithm in detail.
How Dijkstra algorithm Work?
The algorithm works by maintaining a set of vertices that have already been visited, and a set of vertices that have not yet been visited. The algorithm starts at the source vertex and adds it to the set of visited vertices. Then, it repeatedly finds the vertex in the set of unvisited vertices that has the shortest known path to the source vertex, and adds that vertex to the set of visited vertices. This process continues until all vertices have been visited.
The Dijkstra algorithm is a greedy algorithm, which means that it makes the best possible choice at each step, without considering the future consequences of its decisions. In the case of Dijkstra algorithm, the best possible choice is to add the vertex with the shortest known path to the source vertex to the set of visited vertices.
The Dijkstra algorithm is a very efficient algorithm for finding the shortest paths in a graph. Its time complexity is O(V log V), where V is the number of vertices in the graph.
Example of Dijkstra algorithm
Here is an example of Dijkstra algorithm that is discussed below.
Step 1 : Start with a weighted graph.
Step 2 : Choose a starting vertex and assign infinity path values to all other devices.
Step 3 : Go to each vertex and update its path length.
Step 4 : If the path length of the adjacent vertex is less than new path length, don’t update it.
Step 5 : Avoid updating path lengths of already visited vertices.
Step 6 : After each iteration, we pick the unvisited vertex with the least path length. So we choose 5.
Step 7 : Notice how the rightmost vertex has its path length updated twice.
Step 8 : Repeat until all the vertices have been visited.
Pseudocode for Dijkstra algorithm
The following is a pseudocode for Dijkstra algorithm:
procedure Dijkstra(G, s)
for each vertex v in G
dist[v] := infinity
prev[v] := nil
dist[s] := 0
Q := {s}
while Q is not empty
u := vertex in Q with minimum dist[u]
remove u from Q
for each vertex v adjacent to u
if dist[v] > dist[u] + weight(u, v)
dist[v] := dist[u] + weight(u, v)
prev[v] := uIn this pseudocode, G is the graph, s is the source vertex, dist[v] is the shortest known path from s to vertex v, and prev[v] is the predecessor of vertex v in the shortest path from s to v.
Code Implementation of Dijkstra algorithm
Here is a code implementation of the Dijkstra algorithm in C++.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// A structure to represent a weighted edge
struct Edge {
int src;
int dest;
int weight;
};
// A class to represent a graph
class Graph {
private:
int V; // number of vertices
vector<vector<Edge>> adj; // adjacency list
public:
Graph(int V) {
this->V = V;
adj.resize(V);
}
void addEdge(int src, int dest, int weight) {
Edge edge{src, dest, weight};
adj[src].push_back(edge);
}
// Dijkstra's algorithm
void dijkstra(int src, vector<int>& dist) {
// Initialize the distance array
dist.resize(V, INT_MAX);
// Create a priority queue to store the vertices
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// Add the source vertex to the priority queue
pq.push({0, src});
// Mark the source vertex as visited
dist[src] = 0;
while (!pq.empty()) {
// Get the vertex with the shortest distance
int u = pq.top().second;
pq.pop();
// Mark the vertex as visited
visited[u] = true;
// For each unvisited neighbor of u
for (Edge edge : adj[u]) {
int v = edge.dest;
// If the distance to v is greater than the distance to u plus the weight of the edge
if (dist[v] > dist[u] + edge.weight) {
// Update the distance to v
dist[v] = dist[u] + edge.weight;
// Add v to the priority queue
pq.push({dist[v], v});
}
}
}
}
};
int main() {
// Create a graph
Graph g(5);
// Add edges to the graph
g.addEdge(0, 1, 1);
g.addEdge(0, 2, 4);
g.addEdge(1, 2, 2);
g.addEdge(1, 3, 7);
g.addEdge(2, 3, 3);
g.addEdge(2, 4, 5);
g.addEdge(3, 4, 2);
// Initialize the distance array
vector<int> dist(g.V, INT_MAX);
// Run Dijkstra's algorithm
g.dijkstra(0, dist);
// Print the shortest distances from vertex 0 to all other vertices
for (int i = 0; i < g.V; i++) {
cout << "Shortest distance from vertex 0 to vertex " << i << " is " << dist[i] << endl;
}
return 0;
}
Explanation : This code first creates a graph object with 5 vertices. Then, it adds edges to the graph. Next, it initializes the distance array to INT_MAX, which represents infinity. Finally, it runs Dijkstra’s algorithm and prints the shortest distances from vertex 0 to all other vertices.
Applications of Dijkstra algorithm
Dijkstra algorithm is extremely versatile and has a wide range of applications. Among its most common applications are:
- Routing in computer networks
- Finding the shortest path between two points in a road network
- Finding the shortest path between two genes in a DNA sequence
- Finding the shortest path between two products in a supply chain
- Finding the shortest path between two servers in a cloud computing environment
Dijkstra algorithm is also used in a variety of other applications, such as:
- Finding the best route for a robot to navigate through a factory
- Finding the best way to schedule tasks in a manufacturing process
- Finding the best way to allocate resources in a computer system
Complexity of Dijkstra algorithm
The time complexity of Dijkstra algorithm is O(V log V), where V is the number of vertices in the graph. The space complexity of the algorithm is O(V), where V is the number of vertices in the graph.
Some Variations of Dijkstra algorithm
There are many variations of Dijkstra algorithm. Some of the most common variations include:
- The Bellman-Ford algorithm, which is a more general algorithm that can be used to find the shortest paths in graphs with negative weights.
- The Floyd-Warshall algorithm, which is a more efficient algorithm for finding the shortest paths in graphs with dense connectivity.
The algorithm is a more sophisticated algorithm that can be used to find the shortest paths in graphs with obstacles.
Conclusion
Dijkstra algorithm is a powerful and versatile algorithm that can be used to solve a wide variety of problems. It is a fundamental algorithm in computer science and is used in many different applications.
Frequently Asked Questions (FAQs)
Here are some frequently asked questions about Dijkstra algorithm.
1. What is Dijkstra algorithm?
Dijkstra algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
2. What is the problem that Dijkstra algorithm solves?
Dijkstra algorithm solves the single-source shortest path problem. This problem is to find the shortest paths from a single source vertex to all other vertices in a weighted graph.
3. What is the time complexity of Dijkstra algorithm?
The time complexity of Dijkstra algorithm is O(|V|^2), where |V| is the number of vertices in the graph. This is because the algorithm has to examine all of the edges that are adjacent to each vertex.
4. What is the space complexity of Dijkstra algorithm?
The space complexity of Dijkstra algorithm is O(|V|), where |V| is the number of vertices in the graph. This is because the algorithm needs to store the set of visited vertices and the set of unvisited vertices.
5. What are the applications of Dijkstra algorithm?
Dijkstra algorithm is used in a variety of applications, including:
- Routing in road networks
- Finding the shortest path between two websites on the internet
- Finding the shortest path between two genes in a DNA sequence
- Finding the shortest path between two objects in a three-dimensional space