Dijkstra’s algorithm, devised by computer scientist Edsger Dijkstra, is a fundamental graph search algorithm used to find the shortest path between nodes in a weighted graph. In this article, we will learn about how Dijkstra’s algorithm can be used for solving problems in Competitive Programming.
Table of Content
What is Dijkstra’s Algorithm?
Dijkstra’s Algorithm is a Single-Source Shortest Path algorithm, i.e., given a source vertex it finds the shortest path from the source to all other vertices. The idea is to generate a SPT (Shortest Path Tree) with a given source as a root and with two sets,
- one set contains vertices included in the shortest-path tree,
- other set includes vertices not yet included in the shortest-path tree.
At every step of the algorithm, find a vertex that is in the other set (set not yet included) and has a minimum distance from the source.
Dijkstra’s Algorithm uses a Greedy approach to find the shortest path from the source to all other vertices. It starts from the source vertex and maintains a set of vertices with known minimum distances from the source. The key idea of the Greedy strategy is selecting the vertex with the currently shortest known distance from the Source and exploring it next.
Implementation of Dijkstra’s Algorithm:
1. Dense Graph
For Dense Graphs where m is approximately equal to n2 (m= no. of edges and n= no. of vertices) it is optimal to follow the following approach:
- Create two arrays dis[] and vis[]. vis[] is a Boolean array where vis[v] tells whether the vertex v is marked or not (whether the shortest distance from source to vertex v is determined or not) and dis[v] represents minimum distance from source to a marked vertex v.
- Set dis[src]=0 and vis[src]=1, where src is the source node.
- Perform n iterations,
- On each iteration, choose a vertex v with the smallest value of dis[v] and that is unmarked (vis[v] is false). Set vis[v] as true.
- Iterate over all edges (v->u) and set dis[u]=min(dis[u], dis[v]+w), where w is weight of edge from vertex v to u.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// Dijkstra's algorithm for dense graphsvector<int> dijkstra(int n, vector<vector<pair<int, int> > >& adj, int src){ // Array to store minimum distances vector<int> dis(n + 1, INT_MAX); // Array to mark visited vertices vector<bool> vis(n + 1, false); // Set the distance to the source as 0 dis[src] = 0; for (int i = 0; i < n; i++) { int v = -1; for (int j = 1; j <= n; j++) { if (!vis[j] && (v == -1 || dis[j] < dis[v])) v = j; } if (dis[v] == INT_MAX) break; // Mark vertex v as visited vis[v] = true; for (auto edge : adj[v]) { // Neighbor vertex int x = edge.first; // Edge weight int wt = edge.second; // Update the distance if a shorter path is // found if (dis[v] + wt < dis[x]) { dis[x] = dis[v] + wt; } } } // Return the array of minimum distances return dis;}int main(){ // Number of vertices int n = 6; // Adjacency list vector<vector<pair<int, int> > > adj(n + 1); // Example: adding edges to the adjacency list // Edge from vertex 1 to 2 with weight 3 adj[1].push_back({ 2, 3 }); // Edge from vertex 1 to 3 with weight 5 adj[1].push_back({ 3, 5 }); // Edge from vertex 2 to 3 with weight 1 adj[2].push_back({ 3, 1 }); // Edge from vertex 3 to 4 with weight 2 adj[3].push_back({ 4, 2 }); // Edge from vertex 2 to 4 with weight 7 adj[2].push_back({ 4, 7 }); int src = 1; // Source vertex vector<int> distances = dijkstra(n, adj, src); // Print the minimum distances from the source to all // other vertices for (int i = 1; i <= n; i++) { cout << "Minimum distance from vertex " << src << " to " << i << " is " << distances[i] << "\n"; } return 0;} |
C#
using System;using System.Collections.Generic;class Program{ // Dijkstra's algorithm for dense graphs static List<int> Dijkstra(int n, List<List<Tuple<int, int>>> adj, int src) { // Array to store minimum distances List<int> dis = new List<int>(new int[n + 1]); for (int i = 0; i <= n; i++) { dis[i] = int.MaxValue; } // Array to mark visited vertices bool[] vis = new bool[n + 1]; // Set the distance to the source as 0 dis[src] = 0; for (int i = 0; i < n; i++) { int v = -1; for (int j = 1; j <= n; j++) { if (!vis[j] && (v == -1 || dis[j] < dis[v])) v = j; } if (dis[v] == int.MaxValue) break; // Mark vertex v as visited vis[v] = true; foreach (var edge in adj[v]) { // Neighbor vertex int x = edge.Item1; // Edge weight int wt = edge.Item2; // Update the distance if a shorter path is found if (dis[v] + wt < dis[x]) { dis[x] = dis[v] + wt; } } } // Return the list of minimum distances return dis; } static void Main() { // Number of vertices int n = 6; // Adjacency list List<List<Tuple<int, int>>> adj = new List<List<Tuple<int, int>>>(n + 1); for (int i = 0; i <= n; i++) { adj.Add(new List<Tuple<int, int>>()); } // Example: adding edges to the adjacency list // Edge from vertex 1 to 2 with weight 3 adj[1].Add(new Tuple<int, int>(2, 3)); // Edge from vertex 1 to 3 with weight 5 adj[1].Add(new Tuple<int, int>(3, 5)); // Edge from vertex 2 to 3 with weight 1 adj[2].Add(new Tuple<int, int>(3, 1)); // Edge from vertex 3 to 4 with weight 2 adj[3].Add(new Tuple<int, int>(4, 2)); // Edge from vertex 2 to 4 with weight 7 adj[2].Add(new Tuple<int, int>(4, 7)); int src = 1; // Source vertex List<int> distances = Dijkstra(n, adj, src); // Print the minimum distances from the source to all other vertices for (int i = 1; i <= n; i++) { Console.WriteLine($"Minimum distance from vertex {src} to {i} is {distances[i]}"); } }} |
Minimum distance from vertex 1 to 1 is 0 Minimum distance from vertex 1 to 2 is 3 Minimum distance from vertex 1 to 3 is 4 Minimum distance from vertex 1 to 4 is 6 Minimum distance from vertex 1 to 5 ...
Time Complexity: O(n2+m), where n is the number of vertices and m is the number of edges in the given graph.
Auxiliary Space: O(n)
2. Sparse Graph
For Sparse Graph where m is very much smaller than n2, a slightly different implementation is used which is the most optimal in this case:
- In above implementation of dense graph, for selecting the vertex v with smallest value of dis[v], we iterated over all the vertices leading to complexity of O(n) for this operation. Instead of this, we use a data structure (set or priority queue) to extract the vertex with minimum value of dis[v], leading to complexity of O(log n) for this operation.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// Dijkstra algorithm for sparse graphsvector<int> dijkstra(int n, vector<vector<pair<int, int> > >& adj, int src){ // priority_queue to store extract vertex with minimum // distance priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > p; // Array to store minimum distances vector<int> dis(n + 1, INT_MAX); // Push the source vertex with a distance of 0 p.push(make_pair(0, src)); // Set the distance to the source as 0 dis[src] = 0; while (!p.empty()) { int curr = p.top().second; int l = p.top().first; p.pop(); // Skip if this vertex has already been processed // with a shorter distance if (dis[curr] != l) { continue; } for (auto x : adj[curr]) { int d = x.first; // Neighbor vertex int len = x.second; // Edge weight // Update the distance if a shorter path is // found if (dis[d] > len + dis[curr]) { dis[d] = len + dis[curr]; // Push the updated distance and vertex p.push(make_pair(dis[d], d)); } } } // Return the array of minimum distances return dis;}// Driver Codeint main(){ int n = 6; // Number of vertices // Adjacency list vector<vector<pair<int, int> > > adj(n + 1); // Example: adding edges to the adjacency list // Edge from vertex 1 to 2 with weight 3 adj[1].push_back({ 2, 3 }); // Edge from vertex 1 to 3 with weight 5 adj[1].push_back({ 3, 5 }); // Edge from vertex 2 to 3 with weight 1 adj[2].push_back({ 3, 1 }); // Edge from vertex 3 to 4 with weight 2 adj[3].push_back({ 4, 2 }); // Edge from vertex 2 to 4 with weight 7 adj[2].push_back({ 4, 7 }); int src = 1; // Source vertex vector<int> distances = dijkstra(n, adj, src); // Print the minimum distances from the source to all // other vertices for (int i = 1; i <= n; i++) { cout << "Minimum distance from vertex " << src << " to " << i << " is " << distances[i] << "\n"; } return 0;} |
Minimum distance from vertex 1 to 1 is 0 Minimum distance from vertex 1 to 2 is 3 Minimum distance from vertex 1 to 3 is 4 Minimum distance from vertex 1 to 4 is 6 Minimum distance from vertex 1 to 5 ...
Time Complexity: O(mlogn), where n is the number of vertices and m is the number of edges in the given graph.
Auxiliary Space: O(m)
How to solve problems that involve Dijkstra’s Algorithm:
Below are the few problems that will help to identify how or when can we apply Dijkstra’s Algorithm in competitive programming problem:
Problem 1: You are given an undirected weighted graph with N vertices and M edges. You can make the weight of any one edge zero. The task is to compute shortest path from vertex 1 to vertex N such that you can reduce weight of any edge to 0.
Let’s see how we can apply Dijkstra’s Algorithm to above problem:
Observation: The above problem is a shortest path problem but with modification that weight of any one edge can be made 0. Now suppose we are making the weight of edge vertex v and u to 0, then there we get two cases:
Case 1: 1->v->u->N: We need to know the minimum distance between from vertex 1 to vertex v and vertex N to vertex u.
Case 2: 1->u->v->N: We need to know the minimum distance between from vertex 1 to vertex u and vertex N to vertex v.
Applying Dijkstra’s Algorithm: To compute the results of above two cases optimally we use Dijkstra’s Algorithm from vertex 1 and vertex N, since we need to know the minimum distance from vertex 1 and N to every other vertex.
Final Answer: Our final answer will be the minimum of:
min(dis1[v]+dis2[u], dis1[u]+dis2[v]), for all edges(v-u), where dis1[a] represents the minimum distance from vertex 1 to vertex a and dis2[a] represents the minimum distance from vertex N to vertex a.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// Dijkstra's algorithm function to compute minimum// distancesvector<int> Dijkstra(int n, int m, vector<vector<pair<int, int> > >& adj, int src){ // Priority queue for min-heap priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > p; // Initialize distances vector<int> distance(n + 1, INT_MAX); // Push the source vertex with a distance of 0 p.push(make_pair(0, src)); // Set the distance of the source vertex to 0 distance[src] = 0; while (!p.empty()) { int curr = p.top().second; int l = p.top().first; p.pop(); // Skip if this vertex has already been processed // with a shorter distance if (distance[curr] != l) { continue; } // Explore neighbors and update distances for (auto x : adj[curr]) { // Neighbor vertex int d = x.first; // Edge weight int len = x.second; // Update the distance if a shorter path is // found if (distance[d] > len + distance[curr]) { distance[d] = len + distance[curr]; // Push the updated distance and vertex p.push(make_pair(distance[d], d)); } } } return distance;}// Function to solve the problemvoid solve(int n, int m, vector<vector<int> >& edges){ // Adjacency list for edges vector<vector<pair<int, int> > > adj(n + 1); // Build the adjacency list for edges for (int i = 0; i < m; i++) { int x = edges[i][0], y = edges[i][1], z = edges[i][2]; adj[x].push_back({ y, z }); adj[y].push_back({ x, z }); } // Compute minimum distances from vertex 1 and vertex N vector<int> dis1 = Dijkstra(n, m, adj, 1); vector<int> dis2 = Dijkstra(n, m, adj, n); int ans = INT_MAX; // Iterate through all edges to find the minimum cost of // reducing an edge to 0 for (int i = 0; i < m; i++) { int v = edges[i][0], u = edges[i][1]; // Calculate the cost of reducing edge (v, u) to 0 ans = min( ans, min(dis1[v] + dis2[u], dis1[u] + dis2[v])); } // Output the minimum cost cout << ans << "\n";}int main(){ int n = 4, m = 4; // Edges as (vertex1, vertex2, weight) vector<vector<int> > edges = { { 1, 2, 3 }, { 2, 3, 1 }, { 1, 3, 7 }, { 3, 4, 2 } }; // Call the solve function to find the answer solve(n, m, edges);} |
2
Time Complexity: O(mlogn), m is number of edges and n is number of edges.
Auxiliary space: O(n+m),
Problem 2: You are given an undirected weighted graph with N vertices. There are m1 edges which are of TYPE1 and m2 edges which are of TYPE2. The ith TYPE1 edge goes from vertex vi to vertex ui , and weight wi. The ith TYPE2 edge goes from vertex 1 to vertex vi , and weight wi. The task is to determine the maximum TYPE2 edges which can be removed such that the shortest path from vertex 1 to every other vertex remains the same. There can be multiple edges of same type between two vertices.
Let’s see how we can apply Dijkstra’s Algorithm to above problem:
Observation: The ith edge of TYPE 2 which goes from vertex 1 to vertex vi and has weight wi, can be removed if a there exist a path without using this edge such that total distance of this path is less than or equal to wi. We will first use all edges of TYPE 2, and update the dis[] array, dis[i] represents the shortest distance from vertex 1 to vertex ai and create vis[]
Applying Dijkstra’s Algorithm: Choose a vertex v with the smallest value of dis[v] that is unmarked. Set vis[v] as true (mark it). Then iterate over all edges (v->u) , and if dis[v] + w <= dis[u], then we don’t need any edges of TYPE 2 that goes from vertex 1 to vertex u since there exist a path without using the edges (1->u) such that total distance of this path is less than or equal to weight of any edge of TYPE 2 hat goes from vertex 1 to vertex u. We can set ans[u]=false, which indicates that we don’t need any edges of TYPE 2 that goes from vertex 1 to vertex u.
Final answer: If ans[i]=true, then we need a edge of type 2 that goes from vertex 1 to vertex 1. Thus, we can determine at the end the number of vertices i for which ans[i]=true and store it in count.
Hence our final answer will be m2-count, where m2 is the number of edges of TYPE 2 and count is the number of edges of TYPE 2 which are required.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to solve the problemvoid solve(int n, int m1, int m2, vector<vector<int> >& edges1, vector<vector<int> >& edges2){ // Adjacency list for TYPE 1 edges vector<vector<pair<int, int> > > adj(n + 1); // Array to mark which TYPE 2 edges are needed vector<bool> ans(n + 1); // Array to store the shortest distances vector<int> dis(n + 1, INT_MAX); // Build the adjacency list for TYPE 1 edges for (int i = 0; i < m1; i++) { int x = edges1[i][0], y = edges1[i][1], z = edges1[i][2]; adj[x].push_back({ y, z }); adj[y].push_back({ x, z }); } // Initialize dis[] and ans[] arrays for TYPE 2 edges for (int i = 0; i < m2; i++) { int x = edges2[i][0], y = edges2[i][1]; dis[x] = min(dis[x], y); ans[x] = true; } set<pair<int, int> > pq; dis[1] = 0; pq.insert({ 0, 1 }); // Initialize the set with the distances for (int i = 2; i <= n; i++) { if (dis[i] != INT_MAX) { pq.insert({ dis[i], i }); } } // Dijkstra's algorithm while (!pq.empty()) { int curr = (*pq.begin()).second; int l = (*pq.begin()).first; pq.erase(pq.begin()); for (auto x : adj[curr]) { int d = x.first; int len = x.second; // Update the distance and ans[] if a shorter path is found if (dis[d] >= len + dis[curr]) { if (pq.find({ dis[d], d }) != pq.end()) { pq.erase({ dis[d], d }); } dis[d] = len + dis[curr]; pq.insert({ dis[d], d }); ans[d] = false; } } } int count = 0; for (int i = 1; i <= n; i++) { if (ans[i] == true) { count++; } } // Output the maximum number of TYPE 2 edges that can be removed cout << m2 - count << "\n";}int main(){ int n = 5, m1 = 5, m2 = 3; // TYPE1 edges vector<vector<int> > edges1 = { { 1, 2, 1 }, { 2, 3, 2 }, { 1, 3, 3 }, { 3, 4, 4 }, { 1, 5, 5 } }; // TYPE2 edges vector<vector<int> > edges2 = { { 3, 5 }, { 4, 5 }, { 5, 5 } }; // Call the solve function to find the answer solve(n, m1, m2, edges1, edges2);} |
2
Time Complexity: O(mlogn), m is number of edges of TYPE1.
Auxiliary space: O(n+m),
Practice Problems on Dijkstra’s Algorithm for Competitive Programming:
|
Problem |
Problem Link |
|---|---|
|
Shortest Path in a weighted Graph where weight of an edge is 1 or 2 |
Practice Now |
|
Practice Now |
|
|
Practice Now |
|
|
Practice Now |
|
|
Shortest path to reach one prime to other by changing single digit at a time |
|
|
1st to Kth shortest path lengths from node 1 to N in given Graph |
Practice Now |
|
Sum of shortest distance on source to destination and back having at least a common vertex |
Practice Now |
|
Practice Now |
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
