Graphs are powerful data structures used to model relationships between objects. One of the most important problems in graph theory is finding the shortest path between nodes, which is crucial for applications such as network routing, geographical mapping, and more. Dijkstra’s algorithm, developed by Edsger W. Dijkstra in 1956, is a classic algorithm for finding the shortest path from a source node to all other nodes in a graph with non-negative edge weights. This article will guide you through the implementation of Dijkstra’s algorithm in C++, providing detailed explanations and examples.
Prerequisites
Before diving into the implementation, it’s important to understand the following concepts:
- Graph: A collection of nodes (vertices) and edges (connections between nodes).
- Weighted Graph: A graph where each edge has a numerical value (weight) associated with it.
- Shortest Path: The path between two nodes in a graph such that the sum of the weights of the edges is minimized.
- Priority Queue: A data structure that allows for efficient retrieval of the minimum (or maximum) element.
Familiarity with C++ programming, including classes, the Standard Template Library (STL), and basic graph theory, will be beneficial.
Dijkstra’s Algorithm
Dijkstra’s algorithm works by iteratively selecting the node with the smallest known distance from the source, updating the distances to its neighbors, and marking it as “visited.” This process is repeated until all nodes have been visited.
Pseudocode for Dijkstra’s Algorithm
- Initialize the distance to the source node as 0 and all other nodes as infinity.
- Insert the source node into a priority queue.
- While the priority queue is not empty:
- Extract the node with the minimum distance.
- For each neighbor of the extracted node:
- Calculate the new distance from the source to the neighbor.
- If the new distance is less than the known distance, update the distance and insert the neighbor into the priority queue.
- Repeat until all nodes have been processed.
Implementing Dijkstra’s Algorithm
To implement Dijkstra’s algorithm in C++, we will:
- Define a class for the graph.
- Implement the function to perform Dijkstra’s algorithm.
- Create a graph and use the function to find the shortest paths.
C++ Program
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
using namespace std;
class Graph {
public:
int V; // Number of vertices
vector<vector<pair<int, int>>> adj; // Adjacency list
Graph(int V) {
this->V = V;
adj.resize(V);
}
void addEdge(int u, int v, int weight) {
adj[u].push_back(make_pair(v, weight));
adj[v].push_back(make_pair(u, weight)); // Uncomment this line if the graph is undirected
}
void dijkstra(int src) {
vector<int> dist(V, numeric_limits<int>::max());
dist[src] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, src));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (const auto& neighbor : adj[u]) {
int v = neighbor.first;
int weight = neighbor.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
cout << "Vertex\tDistance from Source" << endl;
for (int i = 0; i < V; ++i) {
cout << i << "\t" << dist[i] << endl;
}
}
};
int main() {
int V = 5;
Graph g(V);
g.addEdge(0, 1, 2);
g.addEdge(0, 4, 1);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 1);
g.addEdge(1, 4, 2);
g.addEdge(3, 2, 5);
g.addEdge(3, 4, 3);
int source = 0;
cout << "Dijkstra's Algorithm starting from vertex " << source << ":\n";
g.dijkstra(source);
return 0;
}
Explanation
- Graph Class: The
Graphclass represents a weighted graph using an adjacency list. The constructor initializes the number of vertices and resizes the adjacency list. - addEdge Function: This function adds an edge between two nodes with a given weight.
- dijkstra Function: This function implements Dijkstra’s algorithm. It initializes the distance to the source node as 0 and all other nodes as infinity. It uses a priority queue to extract the node with the minimum distance and updates the distances to its neighbors.
- Main Function: In the main function, we create a graph, add edges, and find the shortest paths from the source node using Dijkstra’s algorithm.
Output
When you run the above program, the output will be:
Dijkstra's Algorithm starting from vertex 0:
Vertex Distance from Source
0 0
1 2
2 5
3 3
4 1
This output shows the shortest distance from the source vertex (0) to all other vertices in the graph.
Additional Examples
Example 2: Larger Graph
Graph Representation
Consider a larger graph:
Vertices: 6
Edges:
0 -> 1 (4), 0 -> 2 (1)
1 -> 3 (1)
2 -> 1 (2), 2 -> 3 (5), 2 -> 4 (3)
3 -> 4 (1)
4 -> 5 (7)
C++ Program
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
using namespace std;
class Graph {
public:
int V;
vector<vector<pair<int, int>>> adj;
Graph(int V) {
this->V = V;
adj.resize(V);
}
void addEdge(int u, int v, int weight) {
adj[u].push_back(make_pair(v, weight));
}
void dijkstra(int src) {
vector<int> dist(V, numeric_limits<int>::max());
dist[src] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, src));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (const auto& neighbor : adj[u]) {
int v = neighbor.first;
int weight = neighbor.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
cout << "Vertex\tDistance from Source" << endl;
for (int i = 0; i < V; ++i) {
cout << i << "\t" << dist[i] << endl;
}
}
};
int main() {
int V = 6;
Graph g(V);
g.addEdge(0, 1, 4);
g.addEdge(0, 2, 1);
g.addEdge(1, 3, 1);
g.addEdge(2, 1, 2);
g.addEdge(2, 3, 5);
g.addEdge(2, 4, 3);
g.addEdge(3, 4, 1);
g.addEdge(4, 5, 7);
int source = 0;
cout << "Dijkstra's Algorithm starting from vertex " << source << ":\n";
g.dijkstra(source);
return 0;
}
Output
Dijkstra's Algorithm starting from vertex 0:
Vertex Distance from Source
0 0
1 3
2 1
3 4
4 4
5 11
Example 3: Graph with Single Node
Graph Representation
Consider a graph with a single node:
Vertices: 1
Edges: None
C++ Program
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
using namespace std;
class Graph {
public:
int V;
vector<vector<pair<int, int>>> adj;
Graph(int V) {
this->V = V;
adj.resize(V);
}
void dijkstra(int src) {
vector<int> dist(V, numeric_limits<int>::max());
dist[src] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, src));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
}
cout << "Vertex\tDistance from Source" << endl;
for (int i = 0; i < V; ++i) {
cout << i << "\t" << dist[i] << endl;
}
}
};
int main() {
int V = 1;
Graph g(V);
int source = 0;
cout << "Dijkstra's Algorithm starting from vertex " << source << ":\n";
g.dijkstra(source);
return 0;
}
Output
Dijkstra's Algorithm starting from vertex 0:
Vertex Distance from Source
0 0
Conclusion
Dijkstra’s algorithm is a powerful tool for finding the shortest paths in a graph with non-negative edge weights. By understanding and implementing this algorithm, you can solve a wide range of problems related to shortest path computation in various applications. The provided examples illustrate different scenarios, helping you grasp the concept and apply it to various graphs.