The shortest path between two vertices (or nodes) in a graph is the path that has the minimum number of edges or the minimum total weight (if the graph is weighted) between the two vertices. In other words, it is the path that requires the least amount of effort or cost to travel from one vertex to the other. Breadth-first search is one algorithm which can be used to find the shortest distance between two nodes in an unweighted graph.
Breadth-first search (aka BFS) is an algorithm that explores all the nodes reachable from the source node in layers. It starts from the source node and visits all nodes at the present “depth” level before moving on to nodes at the next depth level. This guarantees that the first time a node is reached, it is via the shortest path.
In the next sections, first we’ll examine the code to find the shortest distance between a specified start and end node. Next, we’ll enhance this algorithm to determine the shortest distances from the start node to all other nodes in the graph. Finally we will look at code that not only calculates the shortest distance but also prints out a valid shortest path sequence between a given start and end node.
In all the code’s mentioned below, current_layer refers to all nodes in the graph at a depth d from the source node and next_layer refers to all nodes in the graph at a depth d+1 from the source node. Once all the nodes in the current layer are visited, we increment the depth and set next_layer as current_layer.
Finding Shortest Distance Between Two Nodes
Code shown below can be used to compute the shortest distance between a given start node and end node. The find_shortest_distance function performs BFS layer by layer and once the target node is reached, it returns the depth.
Finding Shortest Distance To All Nodes from a Start Node
In order to compute shortest distances from a source node to all other nodes in a graph, we can maintain a distances dictionary which is updated which is updated with the shortest distance for each node when it is first encountered. Below is the implementation:
Finding Shortest Path Between Two Nodes
Code shown below can be used to find the shortest path between a given start node and a target node in the graph. The function find_shortest_path performs a breadth first search on the graph layer by layer and also stores the parent node of each node along the shortest path. Once the target node is reached, the reconstruct_path creates the shortest path sequence between start and target nodes using the parent node information.