Dijkstra's Shortest Path Algorithm using priority_queue of STL
Last Updated : 23 Jul, 2025
Given a graph and a source vertex in graph, find shortest paths from source to all vertices in the given graph.
Input : Source = 0
Output :
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
We have discussed Dijkstra’s shortest Path implementations.
The second implementation is time complexity wise better but is really complex as we have implemented our own priority queue. The Third implementation is simpler as it uses STL. The issue with third implementation is, it uses set which in turn uses Self-Balancing Binary Search Trees. For Dijkstra's algorithm, it is always recommended to use heap (or priority queue) as the required operations (extract minimum and decrease key) match with speciality of heap (or priority queue). However, the problem is, priority_queue doesn't support decrease key. To resolve this problem, do not update a key, but insert one more copy of it. So we allow multiple instances of same vertex in priority queue. This approach doesn't require decrease key operation and has below important properties.
- Whenever distance of a vertex is reduced, we add one more instance of vertex in priority_queue. Even if there are multiple instances, we only consider the instance with minimum distance and ignore other instances.
- The time complexity remains O(ELogV)) as there will be at most O(E) vertices in priority queue and O(Log E) is same as O(Log V)
Below is algorithm based on above idea.
1) Initialize distances of all vertices as infinite.
2) Create an empty priority_queue pq. Every item
of pq is a pair (weight, vertex). Weight (or
distance) is used as first item of pair
as first item is by default used to compare
two pairs
3) Insert source vertex into pq and make its
distance as 0.
4) While either pq doesn't become empty
a) Extract minimum distance vertex from pq.
Let the extracted vertex be u.
b) 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)
(i) Update distance of v, i.e., do
dist[v] = dist[u] + weight(u, v)
(ii) Insert v into the pq (Even if v is
already there)
5) Print distance array dist[] to print all shortest
paths.
Below implementation of above idea:
C++ // Program to find Dijkstra's shortest path using // priority_queue in STL #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f // iPair ==> Integer Pair typedef pair<int, int> iPair; // This class represents a directed graph using // adjacency list representation class Graph { int V; // No. of vertices // In a weighted graph, we need to store vertex // and weight pair for every edge list<pair<int, int> >* adj; public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int u, int v, int w); // prints shortest path from s void shortestPath(int s); }; // Allocates memory for adjacency list Graph::Graph(int V) { this->V = V; adj = new list<iPair>[V]; } void Graph::addEdge(int u, int v, int w) { adj[u].push_back(make_pair(v, w)); adj[v].push_back(make_pair(u, w)); } // Prints shortest paths from src to all other vertices void Graph::shortestPath(int src) { // Create a priority queue to store vertices that // are being preprocessed. This is weird syntax in C++. // Refer below link for details of this syntax // https://www.geeksforgeeks.org/cpp/implement-min-heap-using-stl/ priority_queue<iPair, vector<iPair>, greater<iPair> > pq; // Create a vector for distances and initialize all // distances as infinite (INF) vector<int> dist(V, INF); // Insert source itself in priority queue and initialize // its distance as 0. pq.push(make_pair(0, src)); dist[src] = 0; /* Looping till priority queue becomes empty (or all distances are not finalized) */ while (!pq.empty()) { // The first vertex in pair is the minimum distance // vertex, extract it from priority queue. // vertex label is stored in second of pair (it // has to be done this way to keep the vertices // sorted distance (distance must be first item // in pair) 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)); } } } // Print shortest distances stored in dist[] printf("Vertex Distance from Source\n"); for (int i = 0; i < V; ++i) printf("%d \t\t %d\n", i, dist[i]); } // Driver program to test methods of graph class int main() { // create the graph given in above figure int V = 9; Graph g(V); // making above shown graph g.addEdge(0, 1, 4); 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.shortestPath(0); return 0; } // Java program for the above approach import java.util.*; // Class to represent a graph and implement Dijkstra's // shortest path algorithm class Graph { private int V; // Number of vertices private List<int[]>[] adj; // Adjacency list to store // graph edges // Inner class to represent a pair of vertex and its // weight class iPair implements Comparable<iPair> { int vertex, weight; iPair(int v, int w) { vertex = v; weight = w; } // Comparison method for priority queue public int compareTo(iPair other) { return Integer.compare(this.weight, other.weight); } } // Constructor to initialize the graph Graph(int V) { this.V = V; adj = new ArrayList[V]; for (int i = 0; i < V; ++i) adj[i] = new ArrayList<>(); } // Method to add an edge to the graph void addEdge(int u, int v, int w) { adj[u].add(new int[] { v, w }); adj[v].add(new int[] { u, w }); } // Method to find the shortest paths from source vertex // to all other vertices void shortestPath(int src) { PriorityQueue<iPair> pq = new PriorityQueue<>(); int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); pq.add(new iPair(src, 0)); dist[src] = 0; // Dijkstra's algorithm while (!pq.isEmpty()) { int u = pq.poll().vertex; for (int[] neighbor : adj[u]) { int v = neighbor[0]; int weight = neighbor[1]; // Relaxation step if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; pq.add(new iPair(v, dist[v])); } } } // Print shortest distances from source System.out.println("Vertex Distance from Source"); for (int i = 0; i < V; ++i) System.out.println(i + "\t\t" + dist[i]); } } // Main class containing the main method to test the graph // and Dijkstra's algorithm public class GFG { public static void main(String[] args) { int V = 9; Graph g = new Graph(V); // Adding edges to create the graph g.addEdge(0, 1, 4); 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); // Finding and printing the shortest paths from // source vertex 0 g.shortestPath(0); } } // This code is contributed by Susobhan Akhuli # Python program for the above approach import heapq # This class represents a directed graph using # adjacency list representation class Graph: def __init__(self, V): self.V = V # No. of vertices self.adj = [[] for _ in range(V)] # In a weighted graph, store vertex and weight pair for every edge # Function to add an edge to the graph def add_edge(self, u, v, w): self.adj[u].append((v, w)) self.adj[v].append((u, w)) # Prints shortest paths from src to all other vertices def shortest_path(self, src): # Create a priority queue to store vertices that # are being preprocessed. pq = [(0, src)] # The first element of the tuple is the distance, and the second is the vertex label # Create a list for distances and initialize all # distances as infinite (INF) dist = [float('inf')] * self.V dist[src] = 0 # Looping until the priority queue becomes empty while pq: # The first element in the tuple is the minimum distance vertex # Extract it from the priority queue current_dist, u = heapq.heappop(pq) # Iterate over all adjacent vertices of a vertex for v, weight in self.adj[u]: # If there is a shorter path to v through u if dist[v] > dist[u] + weight: # Update the distance of v dist[v] = dist[u] + weight heapq.heappush(pq, (dist[v], v)) # Print shortest distances print("Vertex Distance from Source") for i in range(self.V): print(f"{i}\t\t{dist[i]}") # Driver program to test methods of the graph class if __name__ == "__main__": # Create the graph given in the above figure V = 9 g = Graph(V) # Making the above-shown graph g.add_edge(0, 1, 4) g.add_edge(0, 7, 8) g.add_edge(1, 2, 8) g.add_edge(1, 7, 11) g.add_edge(2, 3, 7) g.add_edge(2, 8, 2) g.add_edge(2, 5, 4) g.add_edge(3, 4, 9) g.add_edge(3, 5, 14) g.add_edge(4, 5, 10) g.add_edge(5, 6, 2) g.add_edge(6, 7, 1) g.add_edge(6, 8, 6) g.add_edge(7, 8, 7) g.shortest_path(0) # This code is contributed by Susobhan Akhuli // C# program for the above approach using System; using System.Collections.Generic; // Class to represent a graph class Graph { private int V; // No. of vertices private List<Tuple<int, int>>[] adj; // iPair ==> Integer Pair public Graph(int V) { this.V = V; adj = new List<Tuple<int, int>>[V]; for (int i = 0; i < V; ++i) adj[i] = new List<Tuple<int, int>>(); } // function to add an edge to graph public void addEdge(int u, int v, int w) { adj[u].Add(new Tuple<int, int>(v, w)); adj[v].Add(new Tuple<int, int>(u, w)); } // prints shortest paths from src public void shortestPath(int src) { // Create a sorted set to store vertices that // are being preprocessed. SortedSet<Tuple<int, int>> pq = new SortedSet<Tuple<int, int>>(Comparer<Tuple<int, int>>.Create((a, b) => { int cmp = a.Item1.CompareTo(b.Item1); return cmp == 0 ? a.Item2.CompareTo(b.Item2) : cmp; })); // Create a vector for distances and initialize all // distances as infinite (INF) int[] dist = new int[V]; for (int i = 0; i < V; ++i) dist[i] = int.MaxValue; // Insert source itself in the sorted set and initialize // its distance as 0. pq.Add(new Tuple<int, int>(0, src)); dist[src] = 0; /* Looping till the sorted set becomes empty (or all distances are not finalized) */ while (pq.Count > 0) { // The first vertex in tuple is the minimum distance // vertex, extract it from the sorted set. // vertex label is stored in the second element of the tuple. // (it has to be done this way to keep the vertices // sorted by distance, where distance must be the first item // in the tuple) int u = pq.Min.Item2; pq.Remove(pq.Min); // 'i' is used to get all adjacent vertices of a // vertex foreach (var i in adj[u]) { // Get vertex label and weight of the current // adjacent vertex of u. int v = i.Item1; int weight = i.Item2; // If there is a shorter path to v through u. if (dist[v] > dist[u] + weight) { // Updating distance of v pq.Add(new Tuple<int, int>(dist[u] + weight, v)); dist[v] = dist[u] + weight; } } } // Print shortest distances stored in dist[] Console.WriteLine("Vertex Distance from Source"); for (int i = 0; i < V; ++i) Console.WriteLine(i + "\t\t" + dist[i]); } } // Driver program to test methods of the graph class class GFG { static void Main() { // Create the graph given in the above figure int V = 9; Graph g = new Graph(V); // making above shown graph g.addEdge(0, 1, 4); 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.shortestPath(0); } } // This code is contributed by Susobhan Akhuli class PriorityQueue { constructor() { this.queue = []; } enqueue(element) { this.queue.push(element); this.queue.sort((a, b) => a[0] - b[0]); } dequeue() { if (this.isEmpty()) return "Queue is empty"; return this.queue.shift(); } isEmpty() { return this.queue.length === 0; } } class Graph { constructor(V) { this.V = V; this.adj = new Array(V).fill().map(() => []); } addEdge(u, v, w) { this.adj[u].push([v, w]); this.adj[v].push([u, w]); } shortestPath(src) { const pq = new PriorityQueue(); const dist = new Array(this.V).fill(Infinity); pq.enqueue([0, src]); dist[src] = 0; while (!pq.isEmpty()) { const [uDist, u] = pq.dequeue(); for (const [v, weight] of this.adj[u]) { if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; pq.enqueue([dist[v], v]); } } } console.log("Vertex Distance from Source"); for (let i = 0; i < this.V; ++i) { console.log(i + "\t\t" + dist[i]); } } } // Driver program to test methods of the graph class function main() { // create the graph given in the provided C++ code const V = 9; const g = new Graph(V); g.addEdge(0, 1, 4); 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.shortestPath(0); } // Call the main function main(); OutputVertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14
Time complexity : O(E log V)
Space Complexity:O(V2) , here V is number of Vertices.
A Quicker Implementation using vector of pairs representation of weighted graph :
C++ // Program to find Dijkstra's shortest path using // priority_queue in STL #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f // iPair ==> Integer Pair typedef pair<int, int> iPair; // To add an edge void addEdge(vector<pair<int, int> > adj[], int u, int v, int wt) { adj[u].push_back(make_pair(v, wt)); adj[v].push_back(make_pair(u, wt)); } // Prints shortest paths from src to all other vertices void shortestPath(vector<pair<int, int> > adj[], int V, int src) { // Create a priority queue to store vertices that // are being preprocessed. This is weird syntax in C++. // Refer below link for details of this syntax // https://www.geeksforgeeks.org/cpp/implement-min-heap-using-stl/ priority_queue<iPair, vector<iPair>, greater<iPair> > pq; // Create a vector for distances and initialize all // distances as infinite (INF) vector<int> dist(V, INF); // Insert source itself in priority queue and initialize // its distance as 0. pq.push(make_pair(0, src)); dist[src] = 0; /* Looping till priority queue becomes empty (or all distances are not finalized) */ while (!pq.empty()) { // The first vertex in pair is the minimum distance // vertex, extract it from priority queue. // vertex label is stored in second of pair (it // has to be done this way to keep the vertices // sorted distance (distance must be first item // in pair) int u = pq.top().second; pq.pop(); // Get all adjacent of u. for (auto x : adj[u]) { // Get vertex label and weight of current // adjacent of u. int v = x.first; int weight = x.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)); } } } // Print shortest distances stored in dist[] printf("Vertex Distance from Source\n"); for (int i = 0; i < V; ++i) printf("%d \t\t %d\n", i, dist[i]); } // Driver program to test methods of graph class int main() { int V = 9; vector<iPair> adj[V]; // making above shown graph addEdge(adj, 0, 1, 4); addEdge(adj, 0, 7, 8); addEdge(adj, 1, 2, 8); addEdge(adj, 1, 7, 11); addEdge(adj, 2, 3, 7); addEdge(adj, 2, 8, 2); addEdge(adj, 2, 5, 4); addEdge(adj, 3, 4, 9); addEdge(adj, 3, 5, 14); addEdge(adj, 4, 5, 10); addEdge(adj, 5, 6, 2); addEdge(adj, 6, 7, 1); addEdge(adj, 6, 8, 6); addEdge(adj, 7, 8, 7); shortestPath(adj, V, 0); return 0; } // Java program for the above approach import java.util.*; class GFG { private static final int INF = 0x3f3f3f3f; // To add an edge static void addEdge(List<List<Pair<Integer, Integer> > > adj, int u, int v, int wt) { adj.get(u).add(new Pair<>(v, wt)); adj.get(v).add(new Pair<>(u, wt)); } // Prints shortest paths from src to all other vertices static void shortestPath(List<List<Pair<Integer, Integer> > > adj, int V, int src) { // Create a priority queue to store vertices that // are being preprocessed. PriorityQueue<Pair<Integer, Integer> > pq = new PriorityQueue<>( Comparator.comparingInt(Pair::getFirst)); // Create a list for distances and initialize all // distances as infinite (INF) List<Integer> dist = new ArrayList<>(Collections.nCopies(V, INF)); // Insert source itself in priority queue and // initialize its distance as 0. pq.add(new Pair<>(0, src)); dist.set(src, 0); /* Looping till priority queue becomes empty (or all distances are not finalized) */ while (!pq.isEmpty()) { // The first vertex in pair is the minimum // distance vertex, extract it from priority // queue. vertex label is stored in second of // pair (it has to be done this way to keep the // vertices sorted distance (distance must be // first item in pair) int u = pq.peek().getSecond(); pq.poll(); // Get all adjacent of u. for (Pair<Integer, Integer> x : adj.get(u)) { // Get vertex label and weight of current // adjacent of u. int v = x.getFirst(); int weight = x.getSecond(); // If there is a shorter path to v through // u. if (dist.get(v) > dist.get(u) + weight) { // Updating distance of v dist.set(v, dist.get(u) + weight); pq.add(new Pair<>(dist.get(v), v)); } } } // Print shortest distances stored in dist[] System.out.println("Vertex Distance from Source"); for (int i = 0; i < V; i++) { System.out.printf("%d \t\t %d\n", i, dist.get(i)); } } // Driver program to test methods of graph class public static void main(String[] args) { int V = 9; List<List<Pair<Integer, Integer> > > adj = new ArrayList<>(V); for (int i = 0; i < V; i++) { adj.add(new ArrayList<>()); } // Making the above-shown graph addEdge(adj, 0, 1, 4); addEdge(adj, 0, 7, 8); addEdge(adj, 1, 2, 8); addEdge(adj, 1, 7, 11); addEdge(adj, 2, 3, 7); addEdge(adj, 2, 8, 2); addEdge(adj, 2, 5, 4); addEdge(adj, 3, 4, 9); addEdge(adj, 3, 5, 14); addEdge(adj, 4, 5, 10); addEdge(adj, 5, 6, 2); addEdge(adj, 6, 7, 1); addEdge(adj, 6, 8, 6); addEdge(adj, 7, 8, 7); shortestPath(adj, V, 0); } } class Pair<T, U> { private T first; private U second; public Pair(T first, U second) { this.first = first; this.second = second; } public T getFirst() { return first; } public U getSecond() { return second; } } // This code is contributed by Susobhan Akhuli import heapq # Function to add an edge to the adjacency list def addEdge(adj, u, v, wt): adj[u].append((v, wt)) adj[v].append((u, wt)) # Function to find the shortest paths from source to all other vertices def shortestPath(adj, V, src): # Create a priority queue to store vertices that are being preprocessed pq = [] # Create an array for distances and initialize all distances as infinite (INF) dist = [float('inf')] * V # Insert source itself in the priority queue and initialize its distance as 0 heapq.heappush(pq, (0, src)) dist[src] = 0 # Loop until the priority queue becomes empty while pq: # Extract the vertex with minimum distance from the priority queue distance, u = heapq.heappop(pq) # Get all adjacent vertices of u for v, weight in adj[u]: # If there is a shorter path to v through u if dist[v] > dist[u] + weight: # Update distance of v dist[v] = dist[u] + weight heapq.heappush(pq, (dist[v], v)) # Print shortest distances stored in dist[] print("Vertex Distance from Source") for i in range(V): print(i," ",dist[i]) # Main function def main(): V = 9 adj = [[] for _ in range(V)] # Making the graph addEdge(adj, 0, 1, 4) addEdge(adj, 0, 7, 8) addEdge(adj, 1, 2, 8) addEdge(adj, 1, 7, 11) addEdge(adj, 2, 3, 7) addEdge(adj, 2, 8, 2) addEdge(adj, 2, 5, 4) addEdge(adj, 3, 4, 9) addEdge(adj, 3, 5, 14) addEdge(adj, 4, 5, 10) addEdge(adj, 5, 6, 2) addEdge(adj, 6, 7, 1) addEdge(adj, 6, 8, 6) addEdge(adj, 7, 8, 7) # Finding shortest paths from source vertex 0 shortestPath(adj, V, 0) # Call the main function to execute the program if __name__ == "__main__": main() // C# program for the above approach using System; using System.Collections.Generic; // Implement Priority Queue public class PriorityQueue<T> where T : IComparable<T> { private List<T> heap; public PriorityQueue() { heap = new List<T>(); } public int Count => heap.Count; public void Enqueue(T item) { heap.Add(item); int i = heap.Count - 1; while (i > 0) { int parent = (i - 1) / 2; if (heap[parent].CompareTo(heap[i]) <= 0) break; Swap(parent, i); i = parent; } } public T Peek() { if (heap.Count == 0) throw new InvalidOperationException( "Priority queue is empty"); return heap[0]; } public T Dequeue() { if (heap.Count == 0) throw new InvalidOperationException( "Priority queue is empty"); T result = heap[0]; int lastIndex = heap.Count - 1; heap[0] = heap[lastIndex]; heap.RemoveAt(lastIndex); lastIndex--; int current = 0; while (true) { int leftChild = current * 2 + 1; int rightChild = current * 2 + 2; if (leftChild > lastIndex) break; int minChild = leftChild; if (rightChild <= lastIndex && heap[rightChild].CompareTo( heap[leftChild]) < 0) minChild = rightChild; if (heap[current].CompareTo(heap[minChild]) <= 0) break; Swap(current, minChild); current = minChild; } return result; } private void Swap(int i, int j) { T temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } } // To store an integer pair public class Pair : IComparable<Pair> { public int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } public int CompareTo(Pair other) { return this.second.CompareTo(other.second); } } public class GFG { // Function to add an edge to the graph static void AddEdge(List<Pair>[] adj, int u, int v, int wt) { adj[u].Add(new Pair(v, wt)); adj[v].Add(new Pair(u, wt)); } // Function to print shortest paths from source to all // other vertices static void ShortestPath(List<Pair>[] adj, int V, int src) { // Create a priority queue to store vertices that // are being preprocessed PriorityQueue<Pair> pq = new PriorityQueue<Pair>(); // Create an array for distances and initialize all // distances as infinite int[] dist = new int[V]; Array.Fill(dist, int.MaxValue); // Insert source itself in priority queue and // initialize its distance as 0 pq.Enqueue(new Pair(src, 0)); dist[src] = 0; // Loop until priority queue becomes empty while (pq.Count > 0) { // Extract the minimum distance vertex from // priority queue int u = pq.Peek().first; pq.Dequeue(); // Get all adjacent vertices of u foreach(var x in adj[u]) { int v = x.first; int weight = x.second; // If there is a shorter path to v through u if (dist[v] > dist[u] + weight) { // Update distance of v dist[v] = dist[u] + weight; pq.Enqueue(new Pair(v, dist[v])); } } } // Print shortest distances stored in dist[] Console.WriteLine("Vertex Distance from Source"); for (int i = 0; i < V; ++i) { Console.WriteLine($"{i}\t\t{dist[i]}"); } } // Driver program to test methods of graph class static void Main(string[] args) { int V = 9; List<Pair>[] adj = new List<Pair>[ V ]; // Initialize adjacency list for (int i = 0; i < V; i++) { adj[i] = new List<Pair>(); } // Making above shown graph AddEdge(adj, 0, 1, 4); AddEdge(adj, 0, 7, 8); AddEdge(adj, 1, 2, 8); AddEdge(adj, 1, 7, 11); AddEdge(adj, 2, 3, 7); AddEdge(adj, 2, 8, 2); AddEdge(adj, 2, 5, 4); AddEdge(adj, 3, 4, 9); AddEdge(adj, 3, 5, 14); AddEdge(adj, 4, 5, 10); AddEdge(adj, 5, 6, 2); AddEdge(adj, 6, 7, 1); AddEdge(adj, 6, 8, 6); AddEdge(adj, 7, 8, 7); ShortestPath(adj, V, 0); } } // This code is contributed by Susobhan Akhuli // Function to add an edge to the adjacency list function addEdge(adj, u, v, wt) { adj[u].push([v, wt]); adj[v].push([u, wt]); } // Function to find the shortest paths from source to all other vertices function shortestPath(adj, V, src) { // Create a priority queue to store vertices that are being preprocessed let pq = []; // Create an array for distances and initialize all distances as infinite (INF) let dist = new Array(V).fill(Number.POSITIVE_INFINITY); // Insert source itself in the priority queue and initialize its distance as 0 pq.push([0, src]); dist[src] = 0; // Loop until the priority queue becomes empty while (pq.length > 0) { // Extract the vertex with minimum distance from the priority queue let [distance, u] = pq.shift(); // Get all adjacent vertices of u for (let i = 0; i < adj[u].length; i++) { let [v, weight] = adj[u][i]; // If there is a shorter path to v through u if (dist[v] > dist[u] + weight) { // Update distance of v dist[v] = dist[u] + weight; pq.push([dist[v], v]); } } // Sort the priority queue based on distance pq.sort((a, b) => a[0] - b[0]); } // Print shortest distances stored in dist[] console.log("Vertex Distance from Source"); for (let i = 0; i < V; i++) { console.log(i + "\t\t" + dist[i]); } } // Main function function main() { const V = 9; const adj = Array.from({ length: V }, () => []); // Making the graph addEdge(adj, 0, 1, 4); addEdge(adj, 0, 7, 8); addEdge(adj, 1, 2, 8); addEdge(adj, 1, 7, 11); addEdge(adj, 2, 3, 7); addEdge(adj, 2, 8, 2); addEdge(adj, 2, 5, 4); addEdge(adj, 3, 4, 9); addEdge(adj, 3, 5, 14); addEdge(adj, 4, 5, 10); addEdge(adj, 5, 6, 2); addEdge(adj, 6, 7, 1); addEdge(adj, 6, 8, 6); addEdge(adj, 7, 8, 7); // Finding shortest paths from source vertex 0 shortestPath(adj, V, 0); } // Call the main function to execute the program main(); OutputVertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14
The time complexity of Dijkstra's algorithm using a priority queue implemented with a binary heap is O(Elog(V)), where E is the number of edges and V is the number of vertices in the graph.
The space complexity of this implementation is O(V+E), where V is the number of vertices and E is the number of edges.
C++ #include <iostream> #include <vector> #include <queue> #include <unordered_map> using namespace std; // Define a struct Node to store the values struct Node { int v; int distance; // Define a comparator method to compare distance of two nodes bool operator<(const Node& other) const { return distance > other.distance; } }; // Function to implement Dijkstra Algorithm to find shortest distance vector<int> dijkstra(int V, vector<vector<pair<int, int>>>& adj, int S) { // Initialize a visited array and map vector<bool> visited(V, false); unordered_map<int, Node> m; // Initialize a priority queue priority_queue<Node> pq; // Insert source node into map m[S] = {S, 0}; // Add source node to priority queue pq.push({S, 0}); // While the priority queue is not empty while (!pq.empty()) { // Pop the node with the minimum distance from priority queue Node n = pq.top(); pq.pop(); // Get the vertex and distance int v = n.v; int distance = n.distance; // Mark the vertex as visited visited[v] = true; // Get the adjacency list of the vertex vector<pair<int, int>> adjList = adj[v]; // For every adjacent node of the vertex for (const auto& edge : adjList) { // If the node is not yet visited if (!visited[edge.first]) { // If the node is not present in the map if (m.find(edge.first) == m.end()) { // Put the node in the map m[edge.first] = {v, distance + edge.second}; } else { // Get the node from the map Node& sn = m[edge.first]; // Check if the new distance is less than the current distance of the node if (distance + edge.second < sn.distance) { // Update the node's distance sn.v = v; sn.distance = distance + edge.second; } } // Push the node to the priority queue pq.push({edge.first, distance + edge.second}); } } } // Initialize a result vector vector<int> result(V, 0); // For every key in the map for (const auto& entry : m) { // Add the distance of the node to the result result[entry.first] = entry.second.distance; } // Return the result vector return result; } int main() { // Initialize adjacency list and map vector<vector<pair<int, int>>> adj; unordered_map<int, vector<pair<int, int>>> m; // Initialize number of vertices and edges int V = 6; int E = 5; // Define u, v, and w vector<int> u = {0, 0, 1, 2, 4}; vector<int> v = {3, 5, 4, 5, 5}; vector<int> w = {9, 4, 4, 10, 3}; // For every edge for (int i = 0; i < E; ++i) { // Create an edge pair pair<int, int> edge = {v[i], w[i]}; // If u[i] is not present in map if (m.find(u[i]) == m.end()) { // Create a new adjacency list vector<pair<int, int>> adjList; m[u[i]] = adjList; } // Add the edge to the adjacency list m[u[i]].push_back(edge); // Create another edge pair pair<int, int> edge2 = {u[i], w[i]}; // If v[i] is not present in map if (m.find(v[i]) == m.end()) { // Create a new adjacency list vector<pair<int, int>> adjList2; m[v[i]] = adjList2; } // Add the edge to the adjacency list m[v[i]].push_back(edge2); } // For every vertex for (int i = 0; i < V; ++i) { // If the vertex is present in map if (m.find(i) != m.end()) { // Add the adjacency list to the main adjacency list adj.push_back(m[i]); } else { // Add null to the main adjacency list adj.push_back({}); } } // Define source node int S = 1; // Call the dijkstra function vector<int> result = dijkstra(V, adj, S); // Print the result in the specified format cout << "["; for (int i = 0; i < V; ++i) { if (i > 0) { cout << ", "; } cout << result[i]; } cout << "]"; return 0; } import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.PriorityQueue; public class DijkstraAlgoForShortestDistance { static class Node implements Comparable<Node> { int v; int distance; public Node(int v, int distance) { this.v = v; this.distance = distance; } @Override public int compareTo(Node n) { if (this.distance <= n.distance) { return -1; } else { return 1; } } } static int[] dijkstra( int V, ArrayList<ArrayList<ArrayList<Integer> > > adj, int S) { boolean[] visited = new boolean[V]; HashMap<Integer, Node> map = new HashMap<>(); PriorityQueue<Node> q = new PriorityQueue<>(); map.put(S, new Node(S, 0)); q.add(new Node(S, 0)); while (!q.isEmpty()) { Node n = q.poll(); int v = n.v; int distance = n.distance; visited[v] = true; ArrayList<ArrayList<Integer> > adjList = adj.get(v); for (ArrayList<Integer> adjLink : adjList) { if (visited[adjLink.get(0)] == false) { if (!map.containsKey(adjLink.get(0))) { map.put( adjLink.get(0), new Node(v, distance + adjLink.get(1))); } else { Node sn = map.get(adjLink.get(0)); if (distance + adjLink.get(1) < sn.distance) { sn.v = v; sn.distance = distance + adjLink.get(1); } } q.add(new Node(adjLink.get(0), distance + adjLink.get(1))); } } } int[] result = new int[V]; for (int i = 0; i < V; i++) { result[i] = map.get(i).distance; } return result; } public static void main(String[] args) { ArrayList<ArrayList<ArrayList<Integer> > > adj = new ArrayList<>(); HashMap<Integer, ArrayList<ArrayList<Integer> > > map = new HashMap<>(); int V = 6; int E = 5; int[] u = { 0, 0, 1, 2, 4 }; int[] v = { 3, 5, 4, 5, 5 }; int[] w = { 9, 4, 4, 10, 3 }; for (int i = 0; i < E; i++) { ArrayList<Integer> edge = new ArrayList<>(); edge.add(v[i]); edge.add(w[i]); ArrayList<ArrayList<Integer> > adjList; if (!map.containsKey(u[i])) { adjList = new ArrayList<>(); } else { adjList = map.get(u[i]); } adjList.add(edge); map.put(u[i], adjList); ArrayList<Integer> edge2 = new ArrayList<>(); edge2.add(u[i]); edge2.add(w[i]); ArrayList<ArrayList<Integer> > adjList2; if (!map.containsKey(v[i])) { adjList2 = new ArrayList<>(); } else { adjList2 = map.get(v[i]); } adjList2.add(edge2); map.put(v[i], adjList2); } for (int i = 0; i < V; i++) { if (map.containsKey(i)) { adj.add(map.get(i)); } else { adj.add(null); } } int S = 1; // Input sample //[0 [[3, 9], [5, 4]], // 1 [[4, 4]], // 2 [[5, 10]], // 3 [[0, 9]], // 4 [[1, 4], [5, 3]], // 5 [[0, 4], [2, 10], [4, 3]] //] int[] result = DijkstraAlgoForShortestDistance.dijkstra( V, adj, S); System.out.println(Arrays.toString(result)); } } #Python #import modules import heapq #Define a class Node to store the values class Node: def __init__(self, v, distance): self.v = v self.distance = distance #define a comparator method to compare distance of two nodes def __lt__(self, other): return self.distance < other.distance #function to implement Dijkstra Algorithm to find shortest distance def dijkstra(V, adj, S): #initialize a visited list and map visited = [False] * V map = {} #initialize a priority queue q = [] #insert source node in map map[S] = Node(S, 0) #add source node to priority queue heapq.heappush(q, Node(S, 0)) #while the priority queue is not empty while q: #pop the node with minimum distance from priority queue n = heapq.heappop(q) #get the vertex and distance v = n.v distance = n.distance #mark the vertex as visited visited[v] = True #get the adjacent list of the vertex adjList = adj[v] #for every adjacent node of the vertex for edge in adjList: #if the node is not yet visited if visited[edge[0]] == False: #if the node is not present in map if edge[0] not in map: #put the node in map map[edge[0]] = Node(v, distance + edge[1]) else: #get the node from map sn = map[edge[0]] #check if the new distance is less than the current distance of the node if distance + edge[1] < sn.distance: #update the node's distance sn.v = v sn.distance = distance + edge[1] #push the node to priority queue heapq.heappush(q, Node(edge[0], distance + edge[1])) #initialize a result list result = [0] * V #for every key in map for key in map.keys(): #add the distance of the node to the result result[key] = map[key].distance #return the result list return result #main function if __name__ == '__main__': #initialize adjacency list and map adj = [] map = {} #initialize number of vertices and edges V = 6 E = 5 #define u, v and w u = [0, 0, 1, 2, 4] v = [3, 5, 4, 5, 5] w = [9, 4, 4, 10, 3] #for every edge for i in range(E): #create an edge list edge = [v[i], w[i]] #if the u[i] is not present in map if u[i] not in map: #create a new adjacency list adjList = [] else: #get the existing adjacency list adjList = map[u[i]] #add the edge to the adjacency list adjList.append(edge) #put the adjacency list in map map[u[i]] = adjList #create another edge list edge2 = [u[i], w[i]] #if the v[i] is not present in map if v[i] not in map: #create a new adjacency list adjList2 = [] else: #get the existing adjacency list adjList2 = map[v[i]] #add the edge to the adjacency list adjList2.append(edge2) #put the adjacency list in map map[v[i]] = adjList2 #for every vertex for i in range(V): #if the vertex is present in map if i in map: #add the adjacency list to the main adjacency list adj.append(map[i]) else: #add null to the main adjacency list adj.append(None) #define source node S = 1 #call the dijkstra function result = dijkstra(V, adj, S) #print the result print(result) // Define a class Node to store the values class Node { constructor(v, distance) { this.v = v; this.distance = distance; } } // Function to implement Dijkstra Algorithm to find the shortest distance function dijkstra(V, adj, S) { // Initialize a visited list and map let visited = new Array(V).fill(false); let map = {}; // Initialize a priority queue let q = []; // Insert source node in map map[S] = new Node(S, 0); // Add source node to priority queue q.push(new Node(S, 0)); // While the priority queue is not empty while (q.length > 0) { // Pop the node with minimum distance from priority queue let n = q.shift(); // Get the vertex and distance let v = n.v; let distance = n.distance; // Mark the vertex as visited visited[v] = true; // Get the adjacent list of the vertex let adjList = adj[v]; // For every adjacent node of the vertex for (let edge of adjList) { // If the node is not yet visited if (!visited[edge[0]]) { // If the node is not present in map if (!(edge[0] in map)) { // Create a new adjacency list let adjList = []; // Add the node to the adjacency list adjList.push(new Node(v, distance + edge[1])); // Put the adjacency list in map map[edge[0]] = adjList; } else { // Get the existing adjacency list let adjList = map[edge[0]]; // Check if the new distance is less than the current distance of the node if (distance + edge[1] < adjList[0].distance) { // Update the node's distance adjList[0].v = v; adjList[0].distance = distance + edge[1]; } } // Push the node to priority queue q.push(new Node(edge[0], distance + edge[1])); // Sort the priority queue based on distance q.sort((a, b) => a.distance - b.distance); } } } // Initialize a result list let result = new Array(V).fill(0); // For every key in map for (let key in map) { // Check if map[key] is not empty if (map[key].length > 0) { // Add the distance of the node to the result result[key] = map[key][0].distance; } } // Return the result list return result; } // Main function function main() { // Initialize adjacency list and map let adj = []; let map = {}; // Initialize number of vertices and edges let V = 6; let E = 5; // Define u, v, and w let u = [0, 0, 1, 2, 4]; let v = [3, 5, 4, 5, 5]; let w = [9, 4, 4, 10, 3]; // For every edge for (let i = 0; i < E; i++) { // If the u[i] is not present in map if (!(u[i] in map)) { // Create a new adjacency list map[u[i]] = []; } // Add the node to the adjacency list map[u[i]].push([v[i], w[i]]); // If the v[i] is not present in map if (!(v[i] in map)) { // Create a new adjacency list map[v[i]] = []; } // Add the node to the adjacency list map[v[i]].push([u[i], w[i]]); } // For every vertex for (let i = 0; i < V; i++) { // If the vertex is present in map if (i in map) { // Add the adjacency list to the main adjacency list adj.push(map[i]); } else { // Add null to the main adjacency list adj.push(null); } } // Define source node let S = 1; // Call the dijkstra function let result = dijkstra(V, adj, S); // Print the result console.log(result); } // Call the main function main(); // This code is contributed by shivamgupta0987654321 Output[11, 0, 17, 20, 4, 7]
Time Complexity: O(ElogV)
The time complexity is O(ElogV) where E is the number of edges and V is the number of vertices. This is because, for each vertex, we need to traverse all its adjacent vertices and update their distances, which takes O(E) time. Also, we use a Priority Queue which takes O(logV) time for each insertion and deletion.
Space Complexity: O(V)
The space complexity is O(V) as we need to maintain a visited array of size V, a map of size V and a Priority Queue of size V.
Further Optimization We can use a flag array to store what all vertices have been extracted from priority queue. This way we can avoid updating weights of items that have already been extracted.
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem