Problem: Given an unweighted undirected graph, find the shortest path from the given source to the given destination using the depth-first search algorithm.
Since the graph is undirected and connected, there is at least one path between any two vertices of the graph. Therefore it is possible to find the shortest path between any two vertices using the DFS traversal algorithm.
The idea is to successively seek for a smaller path from source to destination vertex using the DFS algorithm.
We explore all possible paths and compare them based on their length. The one with the shortest length is the shortest path between the given vertices.
How to compare length of the possible paths?
We use an integrer length variable to keep count of the number of vertices in the active route (depth) of DFS.
Every time we visit a vertex we increment it by 1.
If the vertex that is being visited is the destination vertex, we compare it with the shortest length of all the discovered paths by then.
How to get route of the shortest path?
we use an extra node property called prev that stores the reference of the preceding vertex for each vertex.
Every time we visit a vertex, we also update its prev value with the last visited vertex.
Using the prev value, we trace the route back from the end vertex to the starting vertex. Example for the given graph, route = E <- B <- A.
Let’s see the implementations of this approach in Python, C++ and Java.
Shortest Path in Graph represented using Adjacency Matrix
Adjacency Matrix is an 2D array that indicates whether the pair of nodes are adjacent or not in the graph.
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | import sys class ShortestPath: def __init__(self, start, end): self.start = start self.end = end self.shortLength = sys.maxsize def findPath(self): #start DFS from the start vertex self.dfs(self.start) #trace the route to output the path self.trace_route() def dfs(self, vertex): global length #Increment the current path length by 1 length +=1 #1st base condition #return if current route is longer #than the already discovered route if length > self.shortLength: return #2nd base condition #if reach the destination vertex #update the shortLength and #return to explore shorter routes if vertex == self.end: self.shortLength = length return #mark vertex as visited to prevent overvisit visited[vertex] = 1 #iterate through all unvisited neighbors vertices for i in range(N): if adjacencyM[vertex][i] == 1 and visited[i] == 0: nbr = i #update the preceding vertex of the neighbors prev[nbr] = vertex #recursively visit the neighbors #to continue search for the destination vertex self.dfs(nbr) #backtrack #visited[vertex] = 0 length -=1 #Function to trace the route using preceding nodes def trace_route(self): vertex = self.end route = [] #start node has no preceding node #so loop until node->prev is null while vertex != -1: route.append(vertices_names[vertex]) vertex = prev[vertex] #reverse the route bring start to the front route.reverse() #output route print(route) if __name__ == '__main__': #vertices or nodes vertices_names = ['A', 'B', 'C', 'D', 'E']; #number of vertices N = len(vertices_names) #Adjacency Matrix adjacencyM = [[0, 1, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 0, 1, 1], [0, 0, 1 ,0, 1], [0, 1, 0, 1, 0]]; #List mapping of vertices to mark them visited visited = [0 for x in range(N)] #List to stores preceding vertices prev = [-1 for x in range(N)] #Driver code sp = ShortestPath(0, 4) length = 0 sp.findPath() |
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <iostream> #include<list> #define N 5 using namespace std; //vertices or nodes char vertices_names[] = {'A', 'B', 'C', 'D', 'E'}; //Adjacency Matrix int adjacencyM[N][N] = {{0, 1, 0, 0, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 1}, {0, 0, 1 ,0, 1}, {0, 1, 0, 1, 0}}; class ShortestPath{ //array to store preceding nodes int prev[N] = {-1}; //array mapping to make visited vertices int visited[N] = {0}; //start and end nodes index int start, end; //variable to store length of the current route int length = 0; //variable to store length of the shortest route int shortLength = INT32_MAX; public: ShortestPath(int start, int end){ this->start = start; this->end = end; } void findPath(){ //start DFS from the start vertex dfs(start); //trace the route to output the path trace_route(); } private: void dfs(int vertex){ //Increment the current path length by 1 length +=1; //1st base condition //return if current route is longer //than the already discovered route if(length > shortLength) return; //2nd base condition //if reach the destination vertex //update the shortLength and //return to explore shorter routes if(vertex == end){ shortLength = length; return; } //mark vertex as visited to prevent overvisit visited[vertex] = 1; //iterate through all unvisited neighbors vertices for(int i=0; i<N; i++){ if(adjacencyM[vertex][i] == 1 and visited[i] == 0){ int nbr = i; //update the preceding vertex of the neighbors prev[nbr] = vertex; //recursively visit the neighbors //to continue search for the destination vertex dfs(nbr); } } //decrement length when tracing back length -=1; } //Function to trace back route void trace_route(){ list<char> route; int vertex = end; //start node has no preceding vertex //so loop until prev[vertex] is -1 while(vertex != -1){ route.push_front(vertices_names[vertex]); vertex = prev[vertex]; } //Display the route for(char n: route){ cout << n <<" "; } } }; int main() { //Driver Code ShortestPath shortestPath(0, 4); shortestPath.findPath(); } |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | import java.util.*; class ShortestPath{ //Adjacency matrix int adjacencyM[][]; //vertices labels char vertices_names[]; //array to store preceding nodes of the traversed vertices int prev[]; //array mapping to make visited vertices int visited[]; //start and end vertices index int start, end; //variable to store length of the current route int length = 0; //variable to store length of the shortest route int shortLength = Integer.MAX_VALUE; ShortestPath(int adjacencyM[][], char[] vertices, int start, int end){ this.adjacencyM = adjacencyM; this.vertices_names = vertices; this.start = start; this.end = end; this.visited = new int[vertices.length]; this.prev = new int[vertices.length]; Arrays.fill(this.prev, -1); } public void findPath(){ //start DFS from the start vertex dfs(start); //trace the route to output the path trace_route(); } private void dfs(int vertex){ //Increment the current path length by 1 length +=1; //1st base condition //return if current route is longer //than the already discovered route if(length > shortLength) return; //2nd base condition //if reach the destination vertex //update the shortLength and //return to explore shorter routes if(vertex == end){ shortLength = length; return; } //mark vertex as visited to prevent overvisit visited[vertex] = 1; //iterate through all unvisited neighbors vertices for(int i=0; i<adjacencyM.length; i++){ if(adjacencyM[vertex][i] == 1 && visited[i] == 0){ int nbr = i; //update the preceding vertex of the neighbors prev[nbr] = vertex; //recursively visit the neighbors //to continue search for the destination vertex dfs(nbr); } } //decrement length when tracing back length -=1; } //Function to trace route using preceding nodes private void trace_route(){ int vertex = end; List<Character> route = new ArrayList<>(); //start vertex has no preceding vertex //so loop until prev[vertex] is -1 while(vertex!=-1){ route.add(vertices_names[vertex]); vertex = prev[vertex]; } //Reverse route to bring start vertex at front Collections.reverse(route); //Output the route System.out.println(route); } } class Main { public static void main(String[] args) { //vertices or nodes array char vertices[] = {'A', 'B', 'C', 'D', 'E'}; //Adjacency Matrix int adjacencyM[][] = {{0, 1, 0, 0, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 1}, {0, 0, 1 ,0, 1}, {0, 1, 0, 1, 0}}; //Driver Code ShortestPath shortestPath = new ShortestPath(adjacencyM, vertices, 0, 4); shortestPath.findPath(); } } |
Output:
[A, B, E]In the above program, the visited array keeps records of the visited vertices and the prev array holds the preceding vertex of each vertex on the corresponding index.
In one of the base conditions, when the length of the active DFS route exceeds the length of the smallest path ever discovered, we deliberately return to look for another way.
Shortest Path in Graph represented using Adjacency List
Every vertex of the graph holds a list of its neighbor (connected) vertices.
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | import sys #class representing vertex of a graph class Vertex: def __init__(self, name): #vertex label self.name = name #variable to hold preceding vertex reference self.prev = None #variable to mark vertex as visited self.visited = False #adjacency list self.neighbors = [] #Method to connect nodes (undirected) def add_neighbor(self, node): self.neighbors.append(node) node.neighbors.append(self) #String representaion of vertex class def __repr__(self): return self.name class ShortestPath: def __init__(self, start, end): #start vertex self.start = start #end vertex self.end = end #hold the length of the active route in DFS self.length =0 #variable to store length of the shortest route self.shortLength = sys.maxsize def findPath(self): #start DFS from the start vertex self.dfs(self.start) #trace the route to output the path self.trace_route() def dfs(self, vertex): #Increment the current path length by 1 self.length +=1 #1st base condition #return if current route is longer #than the already discovered route if self.length > self.shortLength: return #2nd base condition #if reach the destination vertex #update the shortLength and #return to explore shorter routes if vertex == self.end: self.shortLength = self.length return #mark vertex as visited to prevent overvisit vertex.visited = True #iterate through all unvisited neighbors vertices for nbr in vertex.neighbors: if not nbr.visited: #update the preceding vertex of the neighbors nbr.prev = vertex #recursively visit the neighbors #to continue search for the destination vertex self.dfs(nbr) #decrement length when tracing back self.length -=1 #Function to trace the route using preceding nodes def trace_route(self): node = self.end route = [] #start node has no preceding node #so loop until node->prev is null while node: route.append(node) node = node.prev #reverse the route bring start to the front route.reverse() #output route print(route) if __name__ == '__main__': #vertices vertices = [Vertex('A'), Vertex('B'), Vertex('C'), Vertex('D'), Vertex('E')] #connect nodes (i.e. create graph) vertices[0].add_neighbor(vertices[1]) vertices[1].add_neighbor(vertices[2]) vertices[2].add_neighbor(vertices[3]) vertices[3].add_neighbor(vertices[4]) vertices[1].add_neighbor(vertices[4]) #driver code shortestPath = ShortestPath(vertices[0], vertices[4]) shortestPath.findPath() |
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | #include <iostream> #include<list> using namespace std; //class representing vertex of a graph class Vertex{ public: //vertex label char name; //variable to mark vertex as visited bool visited = false; //variable to hold preceding vertex reference Vertex* prev = nullptr; //Adjacency List of the vertex list<Vertex*> neighbors; Vertex(char name){ this->name = name; } //Method to connect vertices (undirected) void add_neighbor(Vertex* v){ this->neighbors.push_back(v); v->neighbors.push_back(this); } }; class ShortestPath{ //start vertex Vertex* start; //end vertex Vertex* end; //variable to store length of the current route int length = 0; //variable to store length of the shortest route int shortLength = INT32_MAX; public: ShortestPath(Vertex* start, Vertex* end){ this->start = start; this->end = end; } void findPath(){ //start DFS from the start vertex dfs(start); //trace the route to output the path trace_route(); } private: void dfs(Vertex* vertex){ //Increment the current path length by 1 length +=1; //1st base condition //return if current route is longer //than the already discovered route if(length > shortLength) return; //2nd base condition //if reach the destination vertex //update the shortLength and //return to explore shorter routes if(vertex == end){ shortLength = length; return; } //mark vertex as visited to prevent overvisit vertex->visited = true; //iterate through all unvisited neighbors vertices for(Vertex* nbr: vertex->neighbors){ if(!nbr->visited){ //update the preceding vertex of the neighbors nbr->prev = vertex; //recursively visit the neighbors //to continue search for the destination vertex dfs(nbr); } } //decrement length when tracing back length -=1; } //Function to trace back route void trace_route(){ list<char> route; Vertex* vertex = end; //start vertex has no preceding vertex //so loop until vertex-> is null while(vertex != nullptr){ route.push_front(vertex->name); vertex = vertex->prev; } //Display the route for(char n: route){ cout << n <<" "; } } }; int main() { //vertices Vertex* vertices[] = {new Vertex('A'), new Vertex('B'),new Vertex('C'),new Vertex('D'),new Vertex('E')}; //connect vertices (i.e. create graph) vertices[0]->add_neighbor(vertices[1]); vertices[1]->add_neighbor(vertices[2]); vertices[2]->add_neighbor(vertices[3]); vertices[3]->add_neighbor(vertices[4]); vertices[1]->add_neighbor(vertices[4]); //Driver Code ShortestPath shortestPath(vertices[0], vertices[4]); shortestPath.findPath(); } |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | import java.util.*; //Class representing a vertex of a graph class Vertex{ //vertex label String name; //Adjacency List List<Vertex> neighbors; //variable to mark vertex as visited boolean visited = false; //variable to hold preceding vertex reference Vertex prev = null; Vertex(String name){ this.name = name; this.neighbors = new ArrayList<>(); } //Method to connect vertices void add_neighbor(Vertex vertex){ this.neighbors.add(vertex); vertex.neighbors.add(this); } //String representation of the class public String toString(){ return this.name; } } class ShortestPath{ //start and end vertex Vertex start, end; //variable to store length of the current route int length = 0; //variable to store length of the shortest route int shortLength = Integer.MAX_VALUE; ShortestPath(Vertex start, Vertex end){ this.start = start; this.end = end; } void findPath(){ //start DFS from the start vertex dfs(start); //trace the route to output the path trace_route(); } private void dfs(Vertex vertex){ //Increment the current path length by 1 length +=1; //1st base condition //return if current route is longer //than the already discovered route if(length > shortLength) return; //2nd base condition //if reach the destination vertex //update the shortLength and //return to explore shorter routes if(vertex == end){ shortLength = length; return; } //mark vertex as visited to prevent overvisit vertex.visited = true; //iterate through all unvisited neighbors vertices for(Vertex nbr: vertex.neighbors){ if(!nbr.visited){ //update the preceding vertex of the neighbors nbr.prev = vertex; //recursively visit the neighbors //to continue search for the destination vertex dfs(nbr); } } //decrement length when tracing back length -=1; } //Function to trace the route private void trace_route(){ Vertex vertex = end; List<Vertex> route = new ArrayList<>(); //preceding vertex of start vertex is null //becasue start.prev == null while(vertex != null){ route.add(vertex); vertex = vertex.prev; } //Reverse the route bring start to the front Collections.reverse(route); //Output the route System.out.println(route); } } class Main { public static void main(String[] args) { //vertices Vertex vertices[] = {new Vertex("A"), new Vertex("B"),new Vertex("C"),new Vertex("D"),new Vertex("E")}; //connect vertices (i.e. create graph) vertices[0].add_neighbor(vertices[1]); vertices[1].add_neighbor(vertices[2]); vertices[2].add_neighbor(vertices[3]); vertices[3].add_neighbor(vertices[4]); vertices[1].add_neighbor(vertices[4]); //Driver Code ShortestPath sp = new ShortestPath(vertices[0], vertices[4]); sp.findPath(); } } |
Output:
[A, B, E]In this method, we represented the vertex of the graph as a class that contains the preceding vertex prev and the visited flag as a member variable.
The time complexity of finding the shortest path using DFS is equal to the complexity of the depth-first search i.e. O(V+E) because in the worst case the algorithm has to cross every vertices and edges of the graph.