# Shortest path in a directed graph by Dijkstra’s algorithm - GeeksforGeeks (2023)

C++ Java Python3 C#

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.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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->add_child(1, 1);`

`v->add_child(2, 4);`

`v->add_child(2, 2);`

`v->add_child(3, 6);`

`v->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;`

`}`

`}`

`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.Add_child(1, 1);`

`v.Add_child(2, 4);`

`v.Add_child(2, 2);`

`v.Add_child(3, 6);`

`v.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`

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: 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

My Personal Notesarrow_drop_up

Top Articles
Latest Posts
Article information

Author: Margart Wisoky

Last Updated: 02/23/2023

Views: 6473

Rating: 4.8 / 5 (58 voted)

Author information

Name: Margart Wisoky

Birthday: 1993-05-13

Address: 2113 Abernathy Knoll, New Tamerafurt, CT 66893-2169

Phone: +25815234346805

Job: Central Developer

Hobby: Machining, Pottery, Rafting, Cosplaying, Jogging, Taekwondo, Scouting

Introduction: My name is Margart Wisoky, I am a gorgeous, shiny, successful, beautiful, adventurous, excited, pleasant person who loves writing and wants to share my knowledge and understanding with you.