Dijkstra’s Algorithm is an important algorithm used for solving the path-finding problem in computer science. This algorithm finds the shortest path from a given node to all other nodes in a graph. It is one of the most popular algorithms in computer science and can be used to solve problems in a wide range of fields from robotics to network routing. In this course, Data Structures and Algorithms with C++, we will be discussing the algorithm in detail and its implementation in C++.
What is Dijkstra’s Algorithm?
Dijkstra’s Algorithm is a graph search algorithm that is used to find the shortest path from a given source node to all other nodes in the graph. The algorithm works by first finding the shortest path from the source node to all other nodes in the graph and then using this information to find the shortest path between any two nodes in the graph.
The algorithm works by first selecting a node from the graph and assigning it a distance value of 0. The algorithm then looks at the neighboring nodes and assigns them a distance value based on their distance from the source node. The algorithm then selects the node with the smallest distance value and updates the distance values for its neighbors. This process is repeated until all the nodes in the graph have been visited.
The Algorithm in C++
In this section, we will be discussing the implementation of Dijkstra’s Algorithm in C++. Before we begin, let’s first discuss the data structure we will be using for the implementation. We will be using an adjacency list for this implementation. An adjacency list is an array of linked lists that stores the neighbors of each node. Each node in the list will store the node’s ID, its distance from the source node, and a pointer to its neighbors.
// The adjacency list data structure
struct Node
{
int id;
int dist;
vector<pair<int,int> > neighbors;
};
Now that we have discussed the data structure, let’s look at the code for the Dijkstra’s Algorithm.
// The function for Dijkstra’s Algorithm
void dijkstra(vector<Node> &graph, int source)
{
// Initialize the distance of all nodes to infinity
vector<int> dist(graph.size(), INT_MAX);
// Create a set to store the nodes that have been visited
set<pair<int, int> > visited;
// Set the distance of the source node to 0
dist[source] = 0;
// Create a priority queue to store the nodes in order of their distance
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
// Push the source node in the priority queue
pq.push(make_pair(dist[source], source));
// While the priority queue is not empty
while (!pq.empty())
{
// Get the node with the minimum distance
int u = pq.top().second;
pq.pop();
// If the node has not been visited
if (visited.find(make_pair(dist[u], u)) == visited.end())
{
// Mark it as visited
visited.insert(make_pair(dist[u], u));
// Update the distance of its neighbors
for (int i = 0; i < graph[u].neighbors.size(); i++)
{
int v = graph[u].neighbors[i].first;
int weight = graph[u].neighbors[i].second;
// If the distance of the neighbor is more than the distance of the source node + the edge weight
if (dist[v] > dist[u] + weight)
{
// Update the distance of the neighbor
dist[v] = dist[u] + weight;
// Push the neighbor in the priority queue
pq.push(make_pair(dist[v], v));
}
}
}
}
// Print the distance of all the nodes
for (int i = 0; i < graph.size(); i++)
cout << i << " " << dist[i] << endl;
}
Time Complexity
The time complexity of Dijkstra’s Algorithm is O(E log V), where E is the number of edges and V is the number of vertices. This makes Dijkstra’s Algorithm one of the most efficient algorithms for finding the shortest path in a graph.
Space Complexity
The space complexity of Dijkstra’s Algorithm is O(V), where V is the number of vertices. This is because the algorithm uses an adjacency list to store the neighbors of each node, which takes up O(V) space.
Conclusion
In this article, we discussed the implementation of Dijkstra’s Algorithm in C++. We discussed the data structure used for the implementation and the code for the algorithm. We also discussed the time and space complexity of the algorithm. As a result, we can conclude that Dijkstra’s Algorithm is an efficient algorithm for finding the shortest path in a graph.
Exercises
Write a program that implements Dijkstra’s Algorithm in C++.
#include <bits/stdc++.h>
using namespace std;
// The adjacency list data structure
struct Node
{
int id;
int dist;
vector<pair<int,int> > neighbors;
};
// The function for Dijkstra’s Algorithm
void dijkstra(vector<Node> &graph, int source)
{
// Initialize the distance of all nodes to infinity
vector<int> dist(graph.size(), INT_MAX);
// Create a set to store the nodes that have been visited
set<pair<int, int> > visited;
// Set the distance of the source node to 0
dist[source] = 0;
// Create a priority queue to store the nodes in order of their distance
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
// Push the source node in the priority queue
pq.push(make_pair(dist[source], source));
// While the priority queue is not empty
while (!pq.empty())
{
// Get the node with the minimum distance
int u = pq.top().second;
pq.pop();
// If the node has not been visited
if (visited.find(make_pair(dist[u], u)) == visited.end())
{
// Mark it as visited
visited.insert(make_pair(dist[u], u));
// Update the distance of its neighbors
for (int i = 0; i < graph[u].neighbors.size(); i++)
{
int v = graph[u].neighbors[i].first;
int weight = graph[u].neighbors[i].second;
// If the distance of the neighbor is more than the distance of the source node + the edge weight
if (dist[v] > dist[u] + weight)
{
// Update the distance of the neighbor
dist[v] = dist[u] + weight;
// Push the neighbor in the priority queue
pq.push(make_pair(dist[v], v));
}
}
}
}
// Print the distance of all the nodes
for (int i = 0; i < graph.size(); i++)
cout << i << " " << dist[i] << endl;
}
int main()
{
// Initialize the graph
vector<Node> graph;
// Add the nodes to the graph
graph.push_back({0, 0, {{1, 3}, {2, 1}}});
graph.push_back({1, INT_MAX, {{3, 4}}});
graph.push_back({2, INT_MAX, {{3, 1}}});
graph.push_back({3, INT_MAX, {}});
// Call the dijkstra function
dijkstra(graph, 0);
return 0;
}
Write a program that finds the shortest path between two given nodes in a graph using Dijkstra’s Algorithm in C++.
#include <bits/stdc++.h>
using namespace std;
// The adjacency list data structure
struct Node
{
int id;
int dist;
vector<pair<int,int> > neighbors;
};
// The function for Dijkstra’s Algorithm
void dijkstra(vector<Node> &graph, int source, int dest)
{
// Initialize the distance of all nodes to infinity
vector<int> dist(graph.size(), INT_MAX);
// Create a set to store the nodes that have been visited
set<pair<int, int> > visited;
// Set the distance of the source node to 0
dist[source] = 0;
// Create a priority queue to store the nodes in order of their distance
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
// Push the source node in the priority queue
pq.push(make_pair(dist[source], source));
// While the priority queue is not empty
while (!pq.empty())
{
// Get the node with the minimum distance
int u = pq.top().second;
pq.pop();
// If the node has not been visited
if (visited.find(make_pair(dist[u], u)) == visited.end())
{
// Mark it as visited
visited.insert(make_pair(dist[u], u));
// Update the distance of its neighbors
for (int i = 0; i < graph[u].neighbors.size(); i++)
{
int v = graph[u].neighbors[i].first;
int weight = graph[u].neighbors[i].second;
// If the distance of the neighbor is more than the distance of the source node + the edge weight
if (dist[v] > dist[u] + weight)
{
// Update the distance of the neighbor
dist[v] = dist[u] + weight;
// Push the neighbor in the priority queue
pq.push(make_pair(dist[v], v));
}
}
}
}
// Print the shortest path from the source to the destination
cout << "The shortest path from " << source << " to " << dest << " is " << dist[dest] << endl;
}
int main()
{
// Initialize the graph
vector<Node> graph;
// Add the nodes to the graph
graph.push_back({0, 0, {{1, 3}, {2, 1}}});
graph.push_back({1, INT_MAX, {{3, 4}}});
graph.push_back({2, INT_MAX, {{3, 1}}});
graph.push_back({3, INT_MAX, {}});
// Call the dijkstra function
dijkstra(graph, 0, 3);
return 0;
}
Write a program that finds the shortest path between all pairs of nodes in a graph using Dijkstra’s Algorithm in C++.
#include <bits/stdc++.h>
using namespace std;
// The adjacency list data structure
struct Node
{
int id;
int dist;
vector<pair<int,int> > neighbors;
};
// The function for Dijkstra’s Algorithm
void dijkstra(vector<Node> &graph, int source)
{
// Initialize the distance of all nodes to infinity
vector<int> dist(graph.size(), INT_MAX);
// Create a set to store the nodes that have been visited
set<pair<int, int> > visited;
// Set the distance of the source node to 0
dist[source] = 0;
// Create a priority queue to store the nodes in order of their distance
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
// Push the source node in the priority queue
pq.push(make_pair(dist[source], source));
// While the priority queue is not empty
while (!pq.empty())
{
// Get the node with the minimum distance
int u = pq.top().second;
pq.pop();
// If the node has not been visited
if (visited.find(make_pair(dist[u], u)) == visited.end())
{
// Mark it as visited
visited.insert(make_pair(dist[u], u));
// Update the distance of its neighbors
for (int i = 0; i < graph[u].neighbors.size(); i++)
{
int v = graph[u].neighbors[i].first;
int weight = graph[u].neighbors[i].second;
// If the distance of the neighbor is more than the distance of the source node + the edge weight
if (dist[v] > dist[u] + weight)
{
// Update the distance of the neighbor
dist[v] = dist[u] + weight;
// Push the neighbor in the priority queue
pq.push(make_pair(dist[v], v));
}
}
}
}
// Print the shortest path from the source to all other nodes
for (int i = 0; i < graph.size(); i++)
cout << "Shortest path from " << source << " to " << i << " is "
<< dist[i] << endl;
return;
}
// Main Function
int main()
{
// Create the graph
vector<Node> graph;
// Add the nodes to the graph
for (int i = 0; i < 5; i++)
{
Node temp;
temp.id = i;
graph.push_back(temp);
}
// Add the edges to the graph
graph[0].neighbors.push_back(make_pair(1, 5));
graph[0].neighbors.push_back(make_pair(2, 10));
graph[0].neighbors.push_back(make_pair(3, 8));
graph[1].neighbors.push_back(make_pair(2, 3));
graph[2].neighbors.push_back(make_pair(3, 2));
graph[3].neighbors.push_back(make_pair(4, 4));
// Find the shortest path from node 0 to all other nodes
dijkstra(graph, 0);
return 0;
}
Write a program to find the shortest path from a given source vertex to all vertices in a unweighted graph using Dijkstra’s Algorithm in C++.
#include <bits/stdc++.h>
using namespace std;
// The adjacency list data structure
struct Node
{
int id;
int dist;
vector<int> neighbors;
};
// The function for Dijkstra’s Algorithm
void dijkstra(vector<Node> &graph, int source)
{
// Initialize the distance of all nodes to infinity
vector<int> dist(graph.size(), INT_MAX);
// Create a set to store the nodes that have been visited
set<pair<int, int> > visited;
// Set the distance of the source node to 0
dist[source] = 0;
// Create a priority queue to store the nodes in order of their distance
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
// Push the source node in the priority queue
pq.push(make_pair(dist[source], source));
// While the priority queue is not empty
while (!pq.empty())
{
// Get the node with the minimum distance
int u = pq.top().second;
pq.pop();
// If the node has not been visited
if (visited.find(make_pair(dist[u], u)) == visited.end())
{
// Mark it as visited
visited.insert(make_pair(dist[u], u));
// Update the distance of its neighbors
for (int i = 0; i < graph[u].neighbors.size(); i++)
{
int v = graph[u].neighbors[i];
// If the distance of the neighbor is more than the distance of the source node + the edge weight
if (dist[v] > dist[u] + 1)
{
// Update the distance of the neighbor
dist[v] = dist[u] + 1;
// Push the neighbor in the priority queue
pq.push(make_pair(dist[v], v));
}
}
}
}
// Print the shortest path from the source to all other nodes
for (int i = 0; i < graph.size(); i++)
cout << "Shortest path from " << source << " to " << i << " is "
<< dist[i] << endl;
return;
}
// Main Function
int main()
{
// Create the graph
vector<Node> graph;
// Add the nodes to the graph
for (int i = 0; i < 5; i++)
{
Node temp;
temp.id = i;
graph.push_back(temp);
}
// Add the edges to the graph
graph[0].neighbors.push_back(1);
graph[0].neighbors.push_back(2);
graph[0].neighbors.push_back(3);
graph[1].neighbors.push_back(2);
graph[2].neighbors.push_back(3);
graph[3].neighbors.push_back(4);
// Find the shortest path from node 0 to all other nodes
dijkstra(graph, 0);
return 0;
}
Write a program to find the shortest path from a given source vertex to all vertices in a weighted graph with negative weights using Dijkstra’s Algorithm in C++.
#include <bits/stdc++.h>
using namespace std;
// The adjacency list data structure
struct Node
{
int id;
int dist;
vector<pair<int,int> > neighbors;
};
// The function for Dijkstra’s Algorithm
void dijkstra(vector<Node> &graph, int source)
{
// Initialize the distance of all nodes to infinity
vector<int> dist(graph.size(), INT_MAX);
// Create a set to store the nodes that have been visited
set<pair<int, int> > visited;
// Set the distance of the source node to 0
dist[source] = 0;
// Create a priority queue to store the nodes in order of their distance
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
// Push the source node in the priority queue
pq.push(make_pair(dist[source], source));
// While the priority queue is not empty
while (!pq.empty())
{
// Get the node with the minimum distance
int u = pq.top().second;
pq.pop();
// If the node has not been visited
if (visited.find(make_pair(dist[u], u)) == visited.end())
{
// Mark it as visited
visited.insert(make_pair(dist[u], u));
// Update the distance of its neighbors
for (int i = 0; i < graph[u].neighbors.size(); i++)
{
int v = graph[u].neighbors[i].first;
int weight = graph[u].neighbors[i].second;
// If the distance of the neighbor is more than the distance of the source node + the edge weight
if (dist[v] > dist[u] + weight)
{
// Update the distance of the neighbor
dist[v] = dist[u] + weight;
// Push the neighbor in the priority queue
pq.push(make_pair(dist[v], v));
}
}
}
}
// Print the shortest path from the source to all other nodes
for (int i = 0; i < graph.size(); i++)
cout << "Shortest path from " << source << " to " << i << " is "
<< dist[i] << endl;
return;
}
// Main Function
int main()
{
// Create the graph
vector<Node> graph;
// Add the nodes to the graph
for (int i = 0; i < 5; i++)
{
Node temp;
temp.id = i;
graph.push_back(temp);
}
// Add the edges to the graph
graph[0].neighbors.push_back(make_pair(1, -5));
graph[0].neighbors.push_back(make_pair(2, -10));
graph[0].neighbors.push_back(make_pair(3, -8));
graph[1].neighbors.push_back(make_pair(2, -3));
graph[2].neighbors.push_back(make_pair(3, -2));
graph[3].neighbors.push_back(make_pair(4, -4));
// Find the shortest path from node 0 to all other nodes
dijkstra(graph, 0);
return 0;
}