Python for Beginners: Shortest Path Length from a Vertex to other Vertices in a Graph

Graphs are used to represent geographical maps, computer networks, etc. In this article, we will discuss how to calculate the shortest distance between vertices in an unweighted graph. To calculate the shortest path length from a vertex to other vertices, we will use breadth first search algorithm.

How to calculate the Shortest Path Length from a Vertex to other vertices?

In an unweighted graph, all the edges have equal weight. It means that we just have to count the number of edges between each vertex to calculate the shortest path length between them. 

For example, consider the following graph.

Graph in Python

Let us calculate the shortest distance between each vertex in the above graph.

There is only one edge E₂ between vertex A and vertex B. So, the shortest path length between them is 1. 

We can reach C from A in two ways. The first one is using the edges E₄-> E₅->E₆ and the second path is using the edges E₂-> E₆. Here, we will choose the shortest path, i.e. E₂-> E₆. Hence the shortest path length between vertex A and vertex C is 2.

There is only one edge E₁ between vertex A and vertex D. So, the shortest path length between them is 1. 

There is only one edge E₃ between vertex A and vertex E. So, the shortest path length between them is 1. 

We can reach F from A in two ways. The first one is using the edges E₂-> E₅ and the second path is using the edges E₄. Here, we will choose the shortest path, i.e. E₄. Hence the shortest path length between vertex A and vertex F is 1.

Algorithm to calculate the Shortest Path Length from a Vertex to other vertices

By now, you must have understood that we have to count the number of edges between the vertices to calculate the distance between the vertices. For this, we will modify the  breadth first search algorithm as follows.

• We will declare a python dictionary that will contain the vertices as their keys and distance from the source vertex as the associated values. 
• Initially, we will assign the distance of each vertex from the source as infinite , denoted by a large number. Whenever we will find a vertex during traversal, we will calculate the current distance of the vertex from the source. If the current distance appears to be less than the distance mentioned in the dictionary containing the distance between source and other vertices, we will update the distance in the dictionary. 
• After full breadth first traversal, we will have the dictionary containing the least distance from the source to each vertex. 

We can formulate the algorithm for calculating the shortest path length between vertices of an unweighted graph as follows.

1. Create an empty Queue Q. 
2. Create a list visited_vertices to keep track of visited vertices.
3. Create a dictionary distance_dict to keep track of distance of vertices from the source vertex. Initialize the distances to 99999999. 
4. Insert source vertex into Q and visited_vertices.
5. If Q is empty, return. Else goto 6.
6. Take out a vertex v from Q.
7. Update the distances of unvisited neighbors of v in distance_dict. 
8. Insert the unvisited neighbors to  Q and visited_vertices.
9. Go to 5.

Implementation

As we have discussed the example and formulated an algorithm to find the shortest path length between source vertex and other vertices in a graph, let us implement the algorithm in python.

from queue import Queue

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def calculate_distance(input_graph, source):
    Q = Queue()
    distance_dict = {k: 999999999 for k in input_graph.keys()}
    visited_vertices = list()
    Q.put(source)
    visited_vertices.append(source)
    while not Q.empty():
        vertex = Q.get()
        if vertex == source:
            distance_dict[vertex] = 0
        for u in input_graph[vertex]:
            if u not in visited_vertices:
                # update the distance
                if distance_dict[u] > distance_dict[vertex] + 1:
                    distance_dict[u] = distance_dict[vertex] + 1
                Q.put(u)
                visited_vertices.append(u)
    return distance_dict


distances = calculate_distance(graph, "A")
for vertex in distances:
    print("Shortest Path Length to {} from {} is {}.".format(vertex, "A", distances[vertex]))

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
Shortest Path Length to A from A is 0.
Shortest Path Length to D from A is 1.
Shortest Path Length to B from A is 1.
Shortest Path Length to C from A is 2.
Shortest Path Length to E from A is 1.

Conclusion

In this article, we have discussed and implemented the algorithm to calculate the shortest path length between vertices in an unweighted graph. Here we have used the breadth first graph traversal algorithm. To read about binary tree traversal algorithms, you can read  Inorder tree traversal algorithm or level order tree traversal algorithm.

The post Shortest Path Length from a Vertex to other Vertices in a Graph appeared first on PythonForBeginners.com.

from Planet Python
via read more