Shortest path in a directed graph by Dijkstra’s algorithm
Given a directed graph and a source vertex in the graph, the task is to find the shortest distance and path from source to target vertex in the given graph where edges are weighted (non-negative) and directed from parent vertex to source vertices.
Approach:
- Mark all vertices unvisited. Create a set of all unvisited vertices.
- Assign zero distance value to source vertex and infinity distance value to all other vertices.
- Set the source vertex as current vertex
- For current vertex, consider all of its unvisited children and calculate their tentative distances through the current. (distance of current + weight of the corresponding edge) Compare the newly calculated distance to the current assigned value (can be infinity for some vertices) and assign the smaller one.
- After considering all the unvisited children of the current vertex, mark the current as visited and remove it from the unvisited set.
- Similarly, continue for all the vertex until all the nodes are visited.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // shortest path in a directed // graph from source vertex to // the destination vertex #include <bits/stdc++.h> #define infi 1000000000 using namespace std; // Class of the node class Node { public : int vertexNumber; // Adjacency list that shows the // vertexNumber of child vertex // and the weight of the edge vector<pair< int , int > > children; Node( int vertexNumber) { this ->vertexNumber = vertexNumber; } // Function to add the child for // the given node void add_child( int vNumber, int length) { pair< int , int > p; p.first = vNumber; p.second = length; children.push_back(p); } }; // Function to find the distance of // the node from the given source // vertex to the destination vertex vector< int > dijkstraDist( vector<Node*> g, int s, vector< int >& path) { // Stores distance of each // vertex from source vertex vector< int > dist(g.size()); // Boolean array that shows // whether the vertex 'i' // is visited or not bool visited[g.size()]; for ( int i = 0; i < g.size(); i++) { visited[i] = false ; path[i] = -1; dist[i] = infi; } dist[s] = 0; path[s] = -1; int current = s; // Set of vertices that has // a parent (one or more) // marked as visited unordered_set< int > sett; while ( true ) { // Mark current as visited visited[current] = true ; for ( int i = 0; i < g[current]->children.size(); i++) { int v = g[current]->children[i].first; if (visited[v]) continue ; // Inserting into the // visited vertex sett.insert(v); int alt = dist[current] + g[current]->children[i].second; // Condition to check the distance // is correct and update it // if it is minimum from the previous // computed distance if (alt < dist[v]) { dist[v] = alt; path[v] = current; } } sett.erase(current); if (sett.empty()) break ; // The new current int minDist = infi; int index = 0; // Loop to update the distance // of the vertices of the graph for ( int a: sett) { if (dist[a] < minDist) { minDist = dist[a]; index = a; } } current = index; } return dist; } // Function to print the path // from the source vertex to // the destination vertex void printPath(vector< int > path, int i, int s) { if (i != s) { // Condition to check if // there is no path between // the vertices if (path[i] == -1) { cout << "Path not found!!" ; return ; } printPath(path, path[i], s); cout << path[i] << " " ; } } // Driver Code int main() { vector<Node*> v; int n = 4, s = 0, e = 5; // Loop to create the nodes for ( int i = 0; i < n; i++) { Node* a = new Node(i); v.push_back(a); } // Creating directed // weighted edges v[0]->add_child(1, 1); v[0]->add_child(2, 4); v[1]->add_child(2, 2); v[1]->add_child(3, 6); v[2]->add_child(3, 3); vector< int > path(v.size()); vector< int > dist = dijkstraDist(v, s, path); // Loop to print the distance of // every node from source vertex for ( int i = 0; i < dist.size(); i++) { if (dist[i] == infi) { cout << i << " and " << s << " are not connected" << endl; continue ; } cout << "Distance of " << i << "th vertex from source vertex " << s << " is: " << dist[i] << endl; } return 0; } |
Java
// Java implementation to find the // shortest path in a directed // graph from source vertex to // the destination vertex import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; class Pair { int first, second; public Pair( int first, int second) { this .first = first; this .second = second; } } public class GFG { static final int infi = 1000000000 ; // Class of the node static class Node { int vertexNumber; // Adjacency list that shows the // vertexNumber of child vertex // and the weight of the edge List<Pair> children; Node( int vertexNumber) { this .vertexNumber = vertexNumber; children = new ArrayList<>(); } // Function to add the child for // the given node void add_child( int vNumber, int length) { Pair p = new Pair(vNumber, length); children.add(p); } } // Function to find the distance of // the node from the given source // vertex to the destination vertex static int [] dijkstraDist(List<Node> g, int s, int [] path) { // Stores distance of each // vertex from source vertex int [] dist = new int [g.size()]; // Boolean array that shows // whether the vertex 'i' // is visited or not boolean [] visited = new boolean [g.size()]; for ( int i = 0 ; i < g.size(); i++) { visited[i] = false ; path[i] = - 1 ; dist[i] = infi; } dist[s] = 0 ; path[s] = - 1 ; int current = s; // Set of vertices that has // a parent (one or more) // marked as visited Set<Integer> sett = new HashSet<>(); while ( true ) { // Mark current as visited visited[current] = true ; for ( int i = 0 ; i < g.get(current).children.size(); i++) { int v = g.get(current).children.get(i).first; if (visited[v]) continue ; // Inserting into the // visited vertex sett.add(v); int alt = dist[current] + g.get(current) .children.get(i) .second; // Condition to check the distance // is correct and update it // if it is minimum from the previous // computed distance if (alt < dist[v]) { dist[v] = alt; path[v] = current; } } sett.remove(current); if (sett.isEmpty()) break ; // The new current int minDist = infi; int index = 0 ; // Loop to update the distance // of the vertices of the graph for ( int a : sett) { if (dist[a] < minDist) { minDist = dist[a]; index = a; } } current = index; } return dist; } // Function to print the path // from the source vertex to // the destination vertex void printPath( int [] path, int i, int s) { if (i != s) { // Condition to check if // there is no path between // the vertices if (path[i] == - 1 ) { System.out.println( "Path not found!!" ); return ; } printPath(path, path[i], s); System.out.print(path[i] + " " ); } } // Driver Code public static void main(String[] args) { List<Node> v = new ArrayList<>(); int n = 4 , s = 0 , e = 5 ; // Loop to create the nodes for ( int i = 0 ; i < n; i++) { Node a = new Node(i); v.add(a); } // Creating directed // weighted edges v.get( 0 ).add_child( 1 , 1 ); v.get( 0 ).add_child( 2 , 4 ); v.get( 1 ).add_child( 2 , 2 ); v.get( 1 ).add_child( 3 , 6 ); v.get( 2 ).add_child( 3 , 3 ); int [] path = new int [v.size()]; int [] dist = dijkstraDist(v, s, path); // Loop to print the distance of // every node from source vertex for ( int i = 0 ; i < dist.length; i++) { if (dist[i] == infi) { System.out.printf( "%d and %d are not " + "connected\n" , i, s); continue ; } System.out.printf( "Distance of %dth vertex " + "from source vertex %d is: %d\n" , i, s, dist[i]); } } } // This code is contributed by sanjeev2552 |
Python3
# Python3 implementation to find the # shortest path in a directed # graph from source vertex to # the destination vertex class Pair: def __init__( self , first, second): self .first = first self .second = second infi = 1000000000 ; # Class of the node class Node: # Adjacency list that shows the # vertexNumber of child vertex # and the weight of the edge def __init__( self , vertexNumber): self .vertexNumber = vertexNumber self .children = [] # Function to add the child for # the given node def Add_child( self , vNumber, length): p = Pair(vNumber, length); self .children.append(p); # Function to find the distance of # the node from the given source # vertex to the destination vertex def dijkstraDist(g, s, path): # Stores distance of each # vertex from source vertex dist = [infi for i in range ( len (g))] # bool array that shows # whether the vertex 'i' # is visited or not visited = [ False for i in range ( len (g))] for i in range ( len (g)): path[i] = - 1 dist[s] = 0 ; path[s] = - 1 ; current = s; # Set of vertices that has # a parent (one or more) # marked as visited sett = set () while ( True ): # Mark current as visited visited[current] = True ; for i in range ( len (g[current].children)): v = g[current].children[i].first; if (visited[v]): continue ; # Inserting into the # visited vertex sett.add(v); alt = dist[current] + g[current].children[i].second; # Condition to check the distance # is correct and update it # if it is minimum from the previous # computed distance if (alt < dist[v]): dist[v] = alt; path[v] = current; if current in sett: sett.remove(current); if ( len (sett) = = 0 ): break ; # The new current minDist = infi; index = 0 ; # Loop to update the distance # of the vertices of the graph for a in sett: if (dist[a] < minDist): minDist = dist[a]; index = a; current = index; return dist; # Function to print the path # from the source vertex to # the destination vertex def printPath(path, i, s): if (i ! = s): # Condition to check if # there is no path between # the vertices if (path[i] = = - 1 ): print ( "Path not found!!" ); return ; printPath(path, path[i], s); print (path[i] + " " ); # Driver Code if __name__ = = '__main__' : v = [] n = 4 s = 0 ; # Loop to create the nodes for i in range (n): a = Node(i); v.append(a); # Creating directed # weighted edges v[ 0 ].Add_child( 1 , 1 ); v[ 0 ].Add_child( 2 , 4 ); v[ 1 ].Add_child( 2 , 2 ); v[ 1 ].Add_child( 3 , 6 ); v[ 2 ].Add_child( 3 , 3 ); path = [ 0 for i in range ( len (v))]; dist = dijkstraDist(v, s, path); # Loop to print the distance of # every node from source vertex for i in range ( len (dist)): if (dist[i] = = infi): print ( "{0} and {1} are not " + "connected" . format (i, s)); continue ; print ( "Distance of {}th vertex from source vertex {} is: {}" . format ( i, s, dist[i])); # This code is contributed by pratham76 |
C#
// C# implementation to find the // shortest path in a directed // graph from source vertex to // the destination vertex using System; using System.Collections; using System.Collections.Generic; class Pair { public int first, second; public Pair( int first, int second) { this .first = first; this .second = second; } } class GFG { static int infi = 1000000000; // Class of the node class Node { public int vertexNumber; // Adjacency list that shows the // vertexNumber of child vertex // and the weight of the edge public List<Pair> children; public Node( int vertexNumber) { this .vertexNumber = vertexNumber; children = new List<Pair>(); } // Function to Add the child for // the given node public void Add_child( int vNumber, int length) { Pair p = new Pair(vNumber, length); children.Add(p); } } // Function to find the distance of // the node from the given source // vertex to the destination vertex static int [] dijkstraDist(List<Node> g, int s, int [] path) { // Stores distance of each // vertex from source vertex int [] dist = new int [g.Count]; // bool array that shows // whether the vertex 'i' // is visited or not bool [] visited = new bool [g.Count]; for ( int i = 0; i < g.Count; i++) { visited[i] = false ; path[i] = -1; dist[i] = infi; } dist[s] = 0; path[s] = -1; int current = s; // Set of vertices that has // a parent (one or more) // marked as visited HashSet< int > sett = new HashSet< int >(); while ( true ) { // Mark current as visited visited[current] = true ; for ( int i = 0; i < g[current].children.Count; i++) { int v = g[current].children[i].first; if (visited[v]) continue ; // Inserting into the // visited vertex sett.Add(v); int alt = dist[current] + g[current].children[i].second; // Condition to check the distance // is correct and update it // if it is minimum from the previous // computed distance if (alt < dist[v]) { dist[v] = alt; path[v] = current; } } sett.Remove(current); if (sett.Count == 0) break ; // The new current int minDist = infi; int index = 0; // Loop to update the distance // of the vertices of the graph foreach ( int a in sett) { if (dist[a] < minDist) { minDist = dist[a]; index = a; } } current = index; } return dist; } // Function to print the path // from the source vertex to // the destination vertex void printPath( int [] path, int i, int s) { if (i != s) { // Condition to check if // there is no path between // the vertices if (path[i] == -1) { Console.WriteLine( "Path not found!!" ); return ; } printPath(path, path[i], s); Console.WriteLine(path[i] + " " ); } } // Driver Code public static void Main( string [] args) { List<Node> v = new List<Node>(); int n = 4, s = 0; // Loop to create the nodes for ( int i = 0; i < n; i++) { Node a = new Node(i); v.Add(a); } // Creating directed // weighted edges v[0].Add_child(1, 1); v[0].Add_child(2, 4); v[1].Add_child(2, 2); v[1].Add_child(3, 6); v[2].Add_child(3, 3); int [] path = new int [v.Count]; int [] dist = dijkstraDist(v, s, path); // Loop to print the distance of // every node from source vertex for ( int i = 0; i < dist.Length; i++) { if (dist[i] == infi) { Console.Write( "{0} and {1} are not " + "connected\n" , i, s); continue ; } Console.Write( "Distance of {0}th vertex " + "from source vertex {1} is: {2}\n" , i, s, dist[i]); } } } // This code is contributed by rutvik_56 |
Javascript
// JavaScript implementation to find the // shortest path in a directed // graph from source vertex to // the destination vertex class Pair { constructor(first, second) { this .first = first; this .second = second; } } const infi = 1000000000; // Class of the node class Node { // Adjacency list that shows the // vertexNumber of child vertex // and the weight of the edge constructor(vertexNumber) { this .vertexNumber = vertexNumber; this .children = []; } // Function to add the child for // the given node Add_child(vNumber, length) { const p = new Pair(vNumber, length); this .children.push(p); } } // Function to find the distance of // the node from the given source // vertex to the destination vertex function dijkstraDist(g, s, path) { // Stores distance of each // vertex from source vertex const dist = new Array(g.length).fill(infi); // bool array that shows // whether the vertex 'i' // is visited or not const visited = new Array(g.length).fill( false ); for (let i = 0; i < g.length; i++) { path[i] = -1; } dist[s] = 0; path[s] = -1; let current = s; // Set of vertices that has // a parent (one or more) // marked as visited const sett = new Set(); while ( true ) { // Mark current as visited visited[current] = true ; for (let i = 0; i < g[current].children.length; i++) { const v = g[current].children[i].first; if (visited[v]) { continue ; } // Inserting into the // visited vertex sett.add(v); const alt = dist[current] + g[current].children[i].second; // Condition to check the distance // is correct and update it // if it is minimum from the previous // computed distance if (alt < dist[v]) { dist[v] = alt; path[v] = current; } } if (sett.has(current)) { sett. delete (current); } if (sett.size === 0) { break ; } // The new current let minDist = infi; let index = 0; // Loop to update the distance // of the vertices of the graph for (const a of sett) { if (dist[a] < minDist) { minDist = dist[a]; index = a; } } current = index; } return dist; } // Function to print the path // from the source vertex to // the destination vertex function printPath(path, i, s) { if (i !== s) { // Condition to check if //there is no path between // the vertices if (path[i] === -1) { console.log( "Path not found!!" ); return ; } printPath(path, path[i], s); console.log(path[i] + " " ); } } // Driver Code let v = []; let n = 4; let s = 0; let e = 5; // Loop to create the nodes for (let i = 0; i < n; i++) { let a = { vertexNumber: i, children: [] }; v.push(a); } // Creating directed // weighted edges v[0].children.push({first: 1, second: 1}); v[0].children.push({first: 2, second: 4}); v[1].children.push({first: 2, second: 2}); v[1].children.push({first: 3, second: 6}); v[2].children.push({first: 3, second: 3}); let path = Array(v.length).fill(-1); let dist = dijkstraDist(v, s, path); // Loop to print the distance of // every node from source vertex for (let i = 0; i < dist.length; i++) { if (dist[i] === infi) { document.write(i + " and " + s + " are not connected" ); continue ; } document.write( "Distance of " + i + "th vertex from source vertex " + s + " is: " + dist[i]); } |
Output
Distance of 0th vertex from source vertex 0 is: 0 Distance of 1th vertex from source vertex 0 is: 1 Distance of 2th vertex from source vertex 0 is: 3 Distance of 3th vertex from source vertex 0 is: 6
Time Complexity: O((E+V)*logV))
Auxiliary Space: O(V + E)
Related articles: We have already discussed the shortest path in directed graph using Topological Sorting, in this article: Shortest path in Directed Acyclic graph