Problem: Given an unweighted undirected graph, find the shortest path from the given source to the given destination using the depth-first search algorithm.

Shortest path in the graph

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.

preceding 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.

Graph represented using Adjacency Matrix

Python

C++

Java

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.

Graph represented using adjacency list

Python

C++

Java

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.

Leave a Reply