Shortest Path Algorithm in Unweighted Graph Using BFS

Breadth First Search for finding shortest path
🔗
Click here to suggest a better video
Click here to view videos suggested by visitors

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.


from collections import deque

# Function to find shortest distance between start and end nodes using BFS
def find_shortest_distance(graph, start, end):
  
  # Initialize the current layer queue and next layer queue
  current_layer = deque([start])
  next_layer = deque()
  
  # Initialize the distance of current layer to 0
  distance = 0
  
  # Initialize the visited set
  visited = set()
  
  # Add the start node to the visited set
  visited.add(start)
  
  # Traverse the graph using BFS
  while current_layer:
    
    # Iterate through the current layer
    for node in current_layer:
      
      # If the current node is the end node, return the distance
      if node == end:
        return distance
      
      # Iterate through the neighbors of the current node
      for neighbor in graph[node]:
        
        # If the neighbor is not visited,
        # add it to the next layer and the visited set
        if neighbor not in visited:
          next_layer.append(neighbor)
          visited.add(neighbor)
    
    # Move to the next layer and increment the distance
    current_layer = next_layer
    next_layer = deque()
    distance += 1
  
  # If the end node is not found, return -1
  return -1
  
graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'C', 'D'],
    'C' : ['A', 'B', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

print("Shortest Distance Between A and F is:")
print(find_shortest_distance(graph, 'A', 'F'))

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:


from collections import deque

# Function to find shortest distance between start and all nodes in a graph using BFS
def bfs_shortest_distance(graph, start):
  # Initialize a dictionary to store distances to each node
  distances = {}
  
  # Initialize two queues for current layer and next layer
  current_layer = deque()
  next_layer = deque()
  
  # Add the start node to the current layer queue and set its distance to 0
  current_layer.append(start)
  distances[start] = 0
  
  # While there are nodes in the current layer queue
  while current_layer:
    # Get the current node from the current layer queue
    current_node = current_layer.popleft()
    
    # Iterate through the neighbors of the current node
    for neighbor in graph[current_node]:
      # If the neighbor has not been visited yet
      if neighbor not in distances:
        # Add the neighbor to the next layer queue
        next_layer.append(neighbor)
        
        # Set the distance of the neighbor to the distance of the current node + 1
        distances[neighbor] = distances[current_node] + 1
    
    # If the current layer queue is empty, swap the current layer and next layer queues
    if not current_layer:
      current_layer, next_layer = next_layer, current_layer
  
  # Return the distances dictionary
  return distances

graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'C', 'D'],
    'C' : ['A', 'B', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

print("Below are all the shortest distances from node A:")
print(bfs_shortest_distance(graph, 'A'))

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.


from collections import deque

# Function to find shortest path sequence between start and end node using BFS
def find_shortest_path(graph, start_node, end_node):
  
  # Initialize two queues, one for current layer and other for next layer
  current_layer = deque()
  next_layer = deque()
  
  # Initialize a dictionary to store parent node for each node
  parent_dict = {}
  
  # Add the start node to the current layer queue and mark it as visited
  current_layer.append(start_node)
  parent_dict[start_node] = None
  
  # Traverse the graph using BFS
  while current_layer:
    
    # Get the current node from the current layer queue
    current_node = current_layer.popleft()
    
    # If the current node is the end node, return the path
    if current_node == end_node:
      return reconstruct_path(parent_dict, start_node, end_node)
    
    # Add all the neighbors of the current node to the next layer queue
    for neighbor in graph[current_node]:
      if neighbor not in parent_dict:
        next_layer.append(neighbor)
        parent_dict[neighbor] = current_node
    
    # If the current layer queue is empty, swap the current and next layer queues
    if not current_layer:
      current_layer, next_layer = next_layer, current_layer
  
  # If the end node is not found, return None
  return None

# Function to reconstruct the shortest path from the parent dictionary
def reconstruct_path(parent_dict, start_node, end_node):
  
  # Initialize the path list
  path = []
  
  # Start from the end node and follow the parent pointers to the start node
  current_node = end_node
  while current_node is not None:
    path.append(current_node)
    current_node = parent_dict[current_node]
  
  # Reverse the path to get the correct order
  path.reverse()
  
  return path

graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'C', 'D'],
    'C' : ['A', 'B', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

print("Shortest Path Between A and F is:")
print(find_shortest_path(graph, 'A', 'F'))