# 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'))
``````