Python program to find Shortest path in an unweighted graph

There are several methods to find Shortest path in an unweighted graph in Python. Some methods are more effective then other while other takes lots of time to give the required result. The most effective and efficient method to find Shortest path in an unweighted graph is called Breadth first search or BFS.

The Time complexity of BFS is O(V + E), where V stands for vertices and E stands for edges.

BFS involves two steps to give the shortest path :

  1. Visiting a vertex
  2. Exploration of vertex

Visiting a vertex means going on a particular vertex while visiting all adjacent vertex of a particular vertex is called exploration of that vertex. Every explored vertex is added to a linear data structure called queue.

Here the trick is to start from any vertex, explore it fully while visiting all its adjacent vertex. While exploration visit adjacent vertex in any order you like. Keep adding the visited vertex into a queue. After you have finished visiting all the adjacent vertex select the next vertex from the queue and repeat the process till all the vertex are visited and the queue is empty.

Implementation of BFS in Python

Lets take the Python example of the following graph and try to find out shortest path in it :

graph = {'1': set(['2', '3']),
         '2': set(['1', '5']),
         '3': set(['1', '4']),
         '4': set(['3','5']),
         '5': set(['2', '4'])}

The resulting graph is undirected with no assigned edge weightings, as length will be evaluated based on the number of path edges traversed.

Now lets find out all the paths between any two vertex of a graph. You may can start from any vertex, then explore it fully, add all the adjacent vertex into a queue. Then select next vertex from the queue.

Given below is a piece of code in Python in order to find out all the path between any two vertex, the first of which being one of the shortest such path. The starting vertex is denoted by S (Source) while the final destination is denoted by D. Starting from S visit all the adjacent vertex of it and add each in a queue. Then take next vertex from queue and repeat the same process until we get all the possible path between the two given vertex.

def bfs(graph, S, D):
    queue = [(S, [S])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == D:
                yield path + [next]
                queue.append((next, path + [next]))

list(bfs(graph, '1', '5'))

The above code give us two possible path between the vertex 1 and 5. If we try to print out the list we get:

[['1', '2', '5'], ['1', '3', '4', '5']]

Knowing that the shortest path will be returned first from the BFS method we can create a useful method that simply returns the shortest path found or ‘None’ if no path exists.

def shortest(graph, S, D):
        return next(bfs(graph, S, D))
    except StopIteration:
        return None

print(shortest(graph, '1', '5'))

The above code will give us the required shortest path. The output of the above code will be:

['1', '2', '5']

Leave a Reply

Your email address will not be published. Required fields are marked *