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:
#include <bits/stdc++.h>
using namespace std;
// Dijkstra's algorithm for dense graphs
vector<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;
}
// Java Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
// Dijkstra's algorithm for dense graphs
static List<Integer> dijkstra(int n, List<List<Pair>> adj, int src) {
// Array to store minimum distances
int[] dis = new int[n + 1];
Arrays.fill(dis, Integer.MAX_VALUE);
// Array to mark visited vertices
boolean[] vis = new boolean[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] == Integer.MAX_VALUE)
break;
// Mark vertex v as visited
vis[v] = true;
for (Pair edge : adj.get(v)) {
// Neighbor vertex
int x = edge.vertex;
// Edge weight
int wt = edge.weight;
// 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
List<Integer> result = new ArrayList<>();
for (int i = 0; i <= n; i++) {
result.add(dis[i]);
}
return result;
}
public static void main(String[] args) {
// Number of vertices
int n = 6;
// Adjacency list
List<List<Pair>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
// Example: adding edges to the adjacency list
// Edge from vertex 1 to 2 with weight 3
adj.get(1).add(new Pair(2, 3));
// Edge from vertex 1 to 3 with weight 5
adj.get(1).add(new Pair(3, 5));
// Edge from vertex 2 to 3 with weight 1
adj.get(2).add(new Pair(3, 1));
// Edge from vertex 3 to 4 with weight 2
adj.get(3).add(new Pair(4, 2));
// Edge from vertex 2 to 4 with weight 7
adj.get(2).add(new Pair(4, 7));
int src = 1; // Source vertex
List<Integer> distances = dijkstra(n, adj, src);
// Print the minimum distances from the source to all other vertices
for (int i = 1; i <= n; i++) {
System.out.println("Minimum distance from vertex " +
src + " to " + i + " is " + distances.get(i));
}
}
static class Pair {
int vertex;
int weight;
Pair(int v, int w) {
vertex = v;
weight = w;
}
}
}
// This code is contributed by Sakshi
import sys
# Dijkstra's algorithm for dense graphs
def dijkstra(n, adj, src):
# Array to store minimum distances
dis = [sys.maxsize] * (n + 1)
# Array to mark visited vertices
vis = [False] * (n + 1)
# Set the distance to the source as 0
dis[src] = 0
for _ in range(n):
v = -1
for j in range(1, n + 1):
if not vis[j] and (v == -1 or dis[j] < dis[v]):
v = j
if dis[v] == sys.maxsize:
break
# Mark vertex v as visited
vis[v] = True
for edge in adj[v]:
# Neighbor vertex
x = edge[0]
# Edge weight
wt = edge[1]
# 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
if __name__ == "__main__":
# Number of vertices
n = 6
# Adjacency list
adj = [[] for _ in range(n + 1)]
# Example: adding edges to the adjacency list
# Edge from vertex 1 to 2 with weight 3
adj[1].append((2, 3))
# Edge from vertex 1 to 3 with weight 5
adj[1].append((3, 5))
# Edge from vertex 2 to 3 with weight 1
adj[2].append((3, 1))
# Edge from vertex 3 to 4 with weight 2
adj[3].append((4, 2))
# Edge from vertex 2 to 4 with weight 7
adj[2].append((4, 7))
src = 1 # Source vertex
distances = dijkstra(n, adj, src)
# Print the minimum distances from the source to all other vertices
for i in range(1, n + 1):
print("Minimum distance from vertex", src, "to", i, "is", distances[i])
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]}");
}
}
}
// JavaScript Implementation
// Function to implement Dijkstra's algorithm for dense graphs
function dijkstra(n, adj, src) {
// Array to store minimum distances
let dis = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER);
// Array to mark visited vertices
let vis = new Array(n + 1).fill(false);
// Set the distance to the source as 0
dis[src] = 0;
for (let i = 0; i < n; i++) {
let v = -1;
for (let j = 1; j <= n; j++) {
if (!vis[j] && (v == -1 || dis[j] < dis[v]))
v = j;
}
if (dis[v] == Number.MAX_SAFE_INTEGER)
break;
// Mark vertex v as visited
vis[v] = true;
for (let edge of adj[v]) {
// Neighbor vertex
let x = edge.vertex;
// Edge weight
let wt = edge.weight;
// 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.slice(1); // Remove the first element (index 0)
}
// Example usage
// Number of vertices
let n = 6;
// Adjacency list
let adj = new Array(n + 1).fill(null).map(() => []);
// Example: adding edges to the adjacency list
// Edge from vertex 1 to 2 with weight 3
adj[1].push({ vertex: 2, weight: 3 });
// Edge from vertex 1 to 3 with weight 5
adj[1].push({ vertex: 3, weight: 5 });
// Edge from vertex 2 to 3 with weight 1
adj[2].push({ vertex: 3, weight: 1 });
// Edge from vertex 3 to 4 with weight 2
adj[3].push({ vertex: 4, weight: 2 });
// Edge from vertex 2 to 4 with weight 7
adj[2].push({ vertex: 4, weight: 7 });
let src = 1; // Source vertex
let distances = dijkstra(n, adj, src);
// Print the minimum distances from the source to all other vertices
for (let i = 1; i <= n; i++) {
console.log(`Minimum distance from vertex ${src} to ${i} is ${distances[i - 1]}`);
}
// Defining Pair class
class Pair {
constructor(v, w) {
this.vertex = v;
this.weight = w;
}
}
Output
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:
#include <bits/stdc++.h>
using namespace std;
// Dijkstra algorithm for sparse graphs
vector<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 Code
int 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;
}
import java.util.*;
public class Dijkstra {
// Pair class to store vertex and weight
static class Pair implements Comparable<Pair> {
int vertex, weight;
// Constructor
public Pair(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
// Comparator for sorting in priority queue based on weight
@Override
public int compareTo(Pair other) {
return Integer.compare(this.weight, other.weight);
}
}
// Dijkstra's algorithm to find the shortest path from src to all other vertices
public static ArrayList<Integer> dijkstra(int n, ArrayList<ArrayList<Pair>> adj, int src) {
PriorityQueue<Pair> pq = new PriorityQueue<>();
ArrayList<Integer> dis = new ArrayList<>(Collections.nCopies(n + 1, Integer.MAX_VALUE));
// Initialize the source distance to 0 and add to priority queue
dis.set(src, 0);
pq.add(new Pair(src, 0));
while (!pq.isEmpty()) {
Pair curr = pq.poll(); // Get and remove the minimum weight pair
int vertex = curr.vertex;
int weight = curr.weight;
// Skip processing if we have already found a better path
if (dis.get(vertex) < weight) continue;
// Explore all adjacent vertices
for (Pair neighbour : adj.get(vertex)) {
// Relaxation step: Check if a better path is found
if (dis.get(neighbour.vertex) > weight + neighbour.weight) {
dis.set(neighbour.vertex, weight + neighbour.weight); // Update distance
pq.add(new Pair(neighbour.vertex, dis.get(neighbour.vertex))); // Add new pair to the queue
}
}
}
return dis; // Return the list of minimum distances
}
public static void main(String[] args) {
int n = 6; // Number of vertices
ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
// Initialize adjacency list
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
// Adding edges to the adjacency list
adj.get(1).add(new Pair(2, 3));
adj.get(1).add(new Pair(3, 5));
adj.get(2).add(new Pair(3, 1));
adj.get(3).add(new Pair(4, 2));
adj.get(2).add(new Pair(4, 7));
int src = 1; // Source vertex
ArrayList<Integer> distances = dijkstra(n, adj, src); // Compute shortest paths
// Print the distances
for (int i = 1; i <= n; i++) {
System.out.println("Minimum distance from vertex " + src + " to " + i + " is " + distances.get(i));
}
}
}
import heapq
# Pair class to store vertex and weight
class Pair:
def __init__(self, vertex, weight):
self.vertex = vertex
self.weight = weight
# Comparator for sorting in priority queue based on weight
def __lt__(self, other):
return self.weight < other.weight
# Dijkstra's algorithm to find the shortest path from src to all other vertices
def dijkstra(n, adj, src):
pq = []
dis = [float('inf')] * (n + 1)
# Initialize the source distance to 0 and add to priority queue
dis[src] = 0
heapq.heappush(pq, Pair(src, 0))
while pq:
curr = heapq.heappop(pq) # Get and remove the minimum weight pair
vertex, weight = curr.vertex, curr.weight
# Skip processing if we have already found a better path
if dis[vertex] < weight:
continue
# Explore all adjacent vertices
for neighbour in adj[vertex]:
# Relaxation step: Check if a better path is found
if dis[neighbour.vertex] > weight + neighbour.weight:
dis[neighbour.vertex] = weight + neighbour.weight # Update distance
heapq.heappush(pq, Pair(neighbour.vertex, dis[neighbour.vertex])) # Add new pair to the queue
return dis # Return the list of minimum distances
if __name__ == "__main__":
n = 6 # Number of vertices
adj = [[] for _ in range(n + 1)]
# Adding edges to the adjacency list
adj[1].append(Pair(2, 3))
adj[1].append(Pair(3, 5))
adj[2].append(Pair(3, 1))
adj[3].append(Pair(4, 2))
adj[2].append(Pair(4, 7))
src = 1 # Source vertex
distances = dijkstra(n, adj, src) # Compute shortest paths
# Print the distances
for i in range(1, n + 1):
print("Minimum distance from vertex {} to {} is {}".format(src, i, distances[i]))
using System;
using System.Collections.Generic;
class DijkstraAlgorithm
{
// Dijkstra algorithm for sparse graphs
static List<int> Dijkstra(int n, List<List<Tuple<int, int>>> adj, int src)
{
// Priority queue to store extracted vertex with minimum distance
PriorityQueue<Tuple<int, int>> p = new PriorityQueue<Tuple<int, int>>();
// 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;
// Push the source vertex with a distance of 0
p.Enqueue(new Tuple<int, int>(0, src));
// Set the distance to the source as 0
dis[src] = 0;
while (p.Count > 0)
{
int curr = p.Peek().Item2;
int l = p.Peek().Item1;
p.Dequeue();
// Skip if this vertex has already been processed with a shorter distance
if (dis[curr] != l)
continue;
foreach (var x in adj[curr])
{
int d = x.Item1; // Neighbor vertex
int len = x.Item2; // 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.Enqueue(new Tuple<int, int>(dis[d], d));
}
}
}
// Return the array of minimum distances
return dis;
}
// Driver Code
static void Main()
{
int n = 6; // Number of vertices
// Adjacency list
List<List<Tuple<int, int>>> adj = new List<List<Tuple<int, int>>>(n + 1);
// Initialize adjacency list
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]}");
}
}
}
// Priority Queue implementation
public class PriorityQueue<T>
{
private List<T> heap;
private Comparison<T> compare;
public int Count { get { return heap.Count; } }
public PriorityQueue() : this(Comparer<T>.Default) { }
public PriorityQueue(IComparer<T> comparer) : this(16, comparer.Compare) { }
public PriorityQueue(Comparison<T> comparison) : this(16, comparison) { }
public PriorityQueue(int capacity, Comparison<T> comparison)
{
this.heap = new List<T>(capacity);
this.compare = comparison;
}
public void Enqueue(T item)
{
heap.Add(item);
int i = Count - 1;
while (i > 0)
{
int j = (i - 1) / 2;
if (compare(heap[j], item) <= 0)
break;
heap[i] = heap[j];
i = j;
}
heap[i] = item;
}
public T Dequeue()
{
T ret = heap[0];
int last = Count - 1;
T x = heap[last];
int i = 0;
while (i * 2 + 1 < last)
{
int a = i * 2 + 1;
int b = i * 2 + 2;
if (b < last && compare(heap[a], heap[b]) > 0) a = b;
if (compare(heap[a], x) >= 0)
break;
heap[i] = heap[a];
i = a;
}
heap[i] = x;
heap.RemoveAt(last);
return ret;
}
public T Peek()
{
return heap[0];
}
}
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(vertex, weight) {
this.queue.push({ vertex, weight });
this.queue.sort((a, b) => a.weight - b.weight);
}
dequeue() {
return this.queue.shift();
}
isEmpty() {
return this.queue.length === 0;
}
}
function dijkstra(n, adj, src) {
const p = new PriorityQueue();
const dis = new Array(n + 1).fill(Number.MAX_VALUE);
p.enqueue(src, 0);
dis[src] = 0;
while (!p.isEmpty()) {
const { vertex: curr, weight: l } = p.dequeue();
if (dis[curr] != l) {
continue;
}
for (const { vertex: d, weight: len } of adj[curr]) {
if (dis[d] > len + dis[curr]) {
dis[d] = len + dis[curr];
p.enqueue(d, dis[d]);
}
}
}
return dis;
}
// Driver code
const n = 6; // Number of vertices
const adj = Array.from({ length: n + 1 }, () => []);
// Example: adding edges to the adjacency list
adj[1].push({ vertex: 2, weight: 3 });
adj[1].push({ vertex: 3, weight: 5 });
adj[2].push({ vertex: 3, weight: 1 });
adj[3].push({ vertex: 4, weight: 2 });
adj[2].push({ vertex: 4, weight: 7 });
const src = 1; // Source vertex
const distances = dijkstra(n, adj, src);
// Print the minimum distances from the source to all other vertices
for (let i = 1; i <= n; i++) {
console.log(`Minimum distance from vertex ${src} to ${i} is ${distances[i]}`);
}
Output
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)
Dijkstra’s Algorithm for Competitive Programming
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?
- Implementation of Dijkstra’s Algorithm
- How to solve problems that involve Dijkstra’s Algorithm
- Practice Problems on Dijkstra’s Algorithm for Competitive Programming