In this tutorial, we will explore how to apply the Dijkstra's algorithm with the priority queue from the C++ STL library. The Dijkstra algorithm serves the purpose of determining the most efficient path between a starting point and a target in an undirected graph.
A graph with weights assigned to its edges is presented as follows:
When selecting a starting point at vertex 0, the objective is to determine the most efficient route from this initial point to every other vertex within the graph.
Source vertex = 0
| Vertex | Distance from source |
|---|---|
0 |
0Same source and destination |
1 |
4Directly goes to 1 |
2 |
12Path: 0 ->1 -> 2(8 + 4 = 12) |
3 |
19Path: 0 ->1 -> 2 -> 3(8 + 4 + 7 = 19) |
4 |
21Path: 0 -> 7 -> 6 -> 5 -> 4(8 + 1 + 2 + 10 = 21) |
5 |
11Path: 0 -> 7 -> 6 -> 5(8 + 1 + 2 = 11) |
6 |
9 Path: 0 -> 7 -> 6(8 + 1 = 9) |
7 |
8Path: 0 -> 7 |
8 |
14Path: 0 -> 1 -> 2 -> 8(4 + 8 + 2 = 14) |
Create graph structure
We are going to establish a Graph class containing the following attributes:
- integer v - This will hold the count of vertices within the graph
- Collection of pairs - This will store both the vertex and the corresponding weight linked to that vertex.
list > *adj;
Constructors:
We require a constructor to reserve memory for the adjacency list.
Example
Graph(int vertex)
{
this->V = vertex; // Allocate the number of vertices
adj = list<pair> [vertex]; // Allocate memory for adjacency list
}
How to add an edge to the graph?
The generated list of pairs consists of two parameters. One parameter will store the vertex, while the other parameter will store the corresponding weight.
Since the graph is bidirectional, we can assign an equal weight to the corresponding vertex in the opposite direction.
Code:
Example
void addanEdge(int u, int v, int w)
{
adj[u].push_back(make_pair(v,w)); // add v to w
adj[v].push_back(make_pair(u,w)); add w to v
// To add a vertex with weight associated with it
}
Algorithm
- Mark initial distance from the source is infinite.
- Create an empty priority_queue PQ. Every item of PQ is a pair (weight, vertex). Weight (or distance) is used as the first item of pair as the first item is by default used to compare two pairs.
- Insert source vertex into PQ and make its distance as 0.
- Until the priority queue defined as PQ does not become empty. Perform the operations a and b. Extract minimum distance vertex from PQ and let it be u. Loop through all adjacent of u and do Following for every vertex v. // If there is a shorter path to v // through u. If dist[v] > dist[u] + weight(u, v) // distance of ( v) > distance of (u) and weight from u to v Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v) Insert v into the pq (Even if v is already there)
- Loop through the dist array to print the shortest paths from source to all the vertices.
- Extract minimum distance vertex from PQ and let it be u.
- Loop through all adjacent of u and do Following for every vertex v. // If there is a shorter path to v // through u. If dist[v] > dist[u] + weight(u, v) // distance of ( v) > distance of (u) and weight from u to v Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v) Insert v into the pq (Even if v is already there)
- Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v)
- Insert v into the pq (Even if v is already there)
C++ code
Example
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f // The distance to other vertices is initialized as infinite
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
class Graph // Graph structure
{
int V; // No. of vertices in the graph
list<pair<int, int>>* adj; // the list of pair to store vertex and its weight
public:
// Constructor that accept number of vertices in graph
Graph(int V) // allocate the vertex memory
{
this->V = V; // assign the vertex
adj = new list<iPair>[V]; // allocate space for vertices
}
void addEdge(int u, int v, int w); // add edges in the graph
// prints shortest path from s
void shortestPathingraph(int s); // pass source vertex
};
void Graph::addEdge(int u, int v, int w) // add an edge
{
adj[u].push_back(make_pair(v, w)); // make a pair of vertex and weight and // add it to the list
adj[v].push_back(make_pair(u, w)); // add oppositely by making a pair of weight and vertex
}
// Calling function outside the Graph class
void Graph::shortestPathingraph(int src) // src is the source vertex
{
// Create a priority queue to store vertices that
// are being preprocessed.
priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
vector<int> dist(V, INF); // All distance from source are infinite
pq.push(make_pair(0, src)); // push spurce node into the queue
dist[src] = 0; // distance of source will be always 0
while (!pq.empty()) { // While queue is not empty
// Extract the first minimum distance from the priority queue
// vertex label is stored in second of pair (it
// has to be done this way to keep the vertices
// sorted distance
int u = pq.top().second;
pq.pop();
// 'i' is used to get all adjacent vertices of a vertex
list<pair<int, int>>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i) {
// Get vertex label and weight of current adjacent
// of u.
int v = (*i).first;
int weight = (*i).second;
// If there is shorted path to v through u.
if (dist[v] > dist[u] + weight) {
// Updating distance of v
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
printf("Vertex \tDistance from Source\n"); // Print the result
for (int i = 0; i < V; ++i)
printf("%d \t\t %d\n", i, dist[i]); // The shortest distance from source
}
int main()
{
int V = 9; // vertices in given graph are 9
Graph g(V); // call Constructor by creating an object of graph
g.addEdge(0, 1, 4); // add root node with neighour vertex and weight
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.shortestPathingraph(0); // call the function to find shortest path of graph
return 0; // end of main function()
}
Output
Output
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
