Shortest Path Algorithm in Unweighted Graph Using BFS

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


#include <iostream>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;

// Function to find shortest distance between start and end nodes using BFS
int find_shortest_distance(unordered_map<char, vector<char>>& graph, char start, char end) {
  // Initialize the current layer queue and next layer queue
  queue<char> current_layer;
  queue<char> next_layer;

  // Initialize the distance of current layer to 0
  int distance = 0;

  // Initialize the visited set
  unordered_set<char> visited;

  // Add the start node to the current layer and the visited set
  current_layer.push(start);
  visited.insert(start);

  // Traverse the graph using BFS
  while (!current_layer.empty()) {
    // Iterate through the current layer
    int current_layer_size = current_layer.size();
    for (int i = 0; i < current_layer_size; i++) {
      char node = current_layer.front();
      current_layer.pop();

      // 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 (char neighbor : graph[node]) {
        // If the neighbor is not visited,
        // add it to the next layer and the visited set
        if (visited.count(neighbor) == 0) {
          next_layer.push(neighbor);
          visited.insert(neighbor);
        }
      }
    }

    // Move to the next layer and increment the distance
    current_layer = move(next_layer);
    distance++;
  }

  // If the end node is not found, return -1
  return -1;
}

int main() {
  // Example graph
  unordered_map<char, vector<char>> graph = {
      {'A', {'B', 'C'}},
      {'B', {'A', 'C', 'D'}},
      {'C', {'A', 'B', 'E', 'F'}},
      {'D', {'B'}},
      {'E', {'C'}},
      {'F', {'C'}}
  };

  cout << "Shortest Distance Between A and F is: " << find_shortest_distance(graph, 'A', 'F') << endl;
  return 0;
}


// Function to find shortest distance between start and end nodes using BFS
function findShortestDistance(graph, start, end) {
  // Initialize the current layer queue and next layer queue
  let currentLayer = [start];
  let nextLayer = [];

  // Initialize the distance of current layer to 0
  let distance = 0;

  // Initialize the visited set
  let visited = new Set();

  // Add the start node to the visited set
  visited.add(start);

  // Traverse the graph using BFS
  while (currentLayer.length > 0) {
    // Iterate through the current layer
    for (let node of currentLayer) {
      // 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 (let neighbor of graph[node]) {
        // If the neighbor is not visited,
        // add it to the next layer and the visited set
        if (!visited.has(neighbor)) {
          nextLayer.push(neighbor);
          visited.add(neighbor);
        }
      }
    }

    // Move to the next layer and increment the distance
    currentLayer = nextLayer;
    nextLayer = [];
    distance += 1;
  }

  // If the end node is not found, return -1
  return -1;
}

// Example usage
const graph = {
  A: ['B', 'C'],
  B: ['A', 'C', 'D'],
  C: ['A', 'B', 'E', 'F'],
  D: ['B'],
  E: ['C'],
  F: ['C']
};

console.log("Shortest Distance Between A and F is:");
console.log(findShortestDistance(graph, 'A', 'F'));


import java.util.*;

public class Main {
  // Function to find shortest distance between start and end nodes using BFS
  public static int findShortestDistance(Map<String, List<String>> graph, String start, String end) {
    // Initialize the current layer queue and next layer queue
    Deque<String> currentLayer = new LinkedList<>();
    Deque<String> nextLayer = new LinkedList<>();

    // Initialize the distance of current layer to 0
    int distance = 0;

    // Initialize the visited set
    Set<String> visited = new HashSet<>();

    // Add the start node to the visited set
    visited.add(start);

    // Add the start node to the current layer queue
    currentLayer.offer(start);

    // Traverse the graph using BFS
    while (!currentLayer.isEmpty()) {
      // Iterate through the current layer
      int currentLayerSize = currentLayer.size();
      for (int i = 0; i < currentLayerSize; i++) {
        String node = currentLayer.poll();

        // If the current node is the end node, return the distance
        if (node.equals(end)) {
          return distance;
        }

        // Iterate through the neighbors of the current node
        for (String neighbor : graph.get(node)) {
          // If the neighbor is not visited,
          // add it to the next layer and the visited set
          if (!visited.contains(neighbor)) {
            nextLayer.offer(neighbor);
            visited.add(neighbor);
          }
        }
      }

      // Move to the next layer and increment the distance
      currentLayer = nextLayer;
      nextLayer = new LinkedList<>();
      distance++;
    }

    // If the end node is not found, return -1
    return -1;
  }

  public static void main(String[] args) {
    // Example graph
    Map<String, List<String>> graph = new HashMap<>();
    graph.put("A", Arrays.asList("B", "C"));
    graph.put("B", Arrays.asList("A", "C", "D"));
    graph.put("C", Arrays.asList("A", "B", "E", "F"));
    graph.put("D", Arrays.asList("B"));
    graph.put("E", Arrays.asList("C"));
    graph.put("F", Arrays.asList("C"));

    System.out.println("Shortest Distance Between A and F is:");
    System.out.println(findShortestDistance(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'))


#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

// Function to find shortest distance between start and all nodes in a graph using BFS
unordered_map<char, int> bfs_shortest_distance(unordered_map<char, vector<char>>& graph, char start) {
  // Initialize a dictionary to store distances to each node
  unordered_map<char, int> distances;
  
  // Initialize two queues for current layer and next layer
  queue<char> current_layer;
  queue<char> next_layer;
  
  // Add the start node to the current layer queue and set its distance to 0
  current_layer.push(start);
  distances[start] = 0;
  
  // While there are nodes in the current layer queue
  while (!current_layer.empty()) {
    // Get the current node from the current layer queue
    char current_node = current_layer.front();
    current_layer.pop();
    
    // Iterate through the neighbors of the current node
    for (char neighbor : graph[current_node]) {
      // If the neighbor has not been visited yet
      if (distances.find(neighbor) == distances.end()) {
        // Add the neighbor to the next layer queue
        next_layer.push(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 (current_layer.empty()) {
      swap(current_layer, next_layer);
    }
  }
  
  // Return the distances dictionary
  return distances;
}

int main() {
  // Example graph
  unordered_map<char, vector<char>> graph = {
      {'A', {'B', 'C'}},
      {'B', {'A', 'C', 'D'}},
      {'C', {'A', 'B', 'E', 'F'}},
      {'D', {'B'}},
      {'E', {'C'}},
      {'F', {'C'}}
  };
  
  cout << "Below are all the shortest distances from node A:" << endl;
  unordered_map<char, int> distances = bfs_shortest_distance(graph, 'A');
  for (auto& [node, distance] : distances) {
    cout << "Distance to node " << node << ": " << distance << endl;
  }
  
  return 0;
}


// Function to find shortest distance between start and all nodes in a graph using BFS
function bfsShortestDistance(graph, start) {
  // Initialize a dictionary to store distances to each node
  const distances = {};

  // Initialize two queues for current layer and next layer
  const currentLayer = [];
  const nextLayer = [];

  // Add the start node to the current layer queue and set its distance to 0
  currentLayer.push(start);
  distances[start] = 0;

  // While there are nodes in the current layer queue
  while (currentLayer.length > 0) {
    // Get the current node from the current layer queue
    const currentNode = currentLayer.shift();

    // Iterate through the neighbors of the current node
    for (const neighbor of graph[currentNode]) {
      // If the neighbor has not been visited yet
      if (!(neighbor in distances)) {
        // Add the neighbor to the next layer queue
        nextLayer.push(neighbor);

        // Set the distance of the neighbor to the distance of the current node + 1
        distances[neighbor] = distances[currentNode] + 1;
      }
    }

    // If the current layer queue is empty, swap the current layer and next layer queues
    if (currentLayer.length === 0) {
      [currentLayer, nextLayer] = [nextLayer, currentLayer];
    }
  }

  // Return the distances dictionary
  return distances;
}

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

console.log("Below are all the shortest distances from node A:");
console.log(bfsShortestDistance(graph, 'A'));


import java.util.*;

public class Main {
  // Function to find shortest distance between start and all nodes in a graph using BFS
  public static Map<String, Integer> bfsShortestDistance(Map<String, List<String>> graph, String start) {
    // Initialize a dictionary to store distances to each node
    Map<String, Integer> distances = new HashMap<>();

    // Initialize two queues for current layer and next layer
    Queue<String> currentLayer = new LinkedList<>();
    Queue<String> nextLayer = new LinkedList<>();

    // Add the start node to the current layer queue and set its distance to 0
    currentLayer.offer(start);
    distances.put(start, 0);

    // While there are nodes in the current layer queue
    while (!currentLayer.isEmpty()) {
      // Get the current node from the current layer queue
      String currentNode = currentLayer.poll();

      // Iterate through the neighbors of the current node
      for (String neighbor : graph.get(currentNode)) {
        // If the neighbor has not been visited yet
        if (!distances.containsKey(neighbor)) {
          // Add the neighbor to the next layer queue
          nextLayer.offer(neighbor);

          // Set the distance of the neighbor to the distance of the current node + 1
          distances.put(neighbor, distances.get(currentNode) + 1);
        }
      }

      // If the current layer queue is empty, swap the current layer and next layer queues
      if (currentLayer.isEmpty()) {
        currentLayer = nextLayer;
        nextLayer = new LinkedList<>();
      }
    }

    // Return the distances dictionary
    return distances;
  }

  public static void main(String[] args) {
    // Sample graph
    Map<String, List<String>> graph = new HashMap<>();
    graph.put("A", Arrays.asList("B", "C"));
    graph.put("B", Arrays.asList("A", "C", "D"));
    graph.put("C", Arrays.asList("A", "B", "E", "F"));
    graph.put("D", Arrays.asList("B"));
    graph.put("E", Arrays.asList("C"));
    graph.put("F", Arrays.asList("C"));

    System.out.println("Below are all the shortest distances from node A:");
    System.out.println(bfsShortestDistance(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'))


#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

// Function to reconstruct the shortest path from the parent dictionary
vector<string> reconstruct_path(unordered_map<string, string>& parent_dict, string start_node, string end_node) {
  // Initialize the path list
  vector<string> path;

  // Start from the end node and follow the parent pointers to the start node
  string current_node = end_node;
  while (current_node != "") {
    path.insert(path.begin(), current_node);
    current_node = parent_dict[current_node];
  }

  return path;
}

// Function to find shortest path sequence between start and end node using BFS
vector<string> find_shortest_path(unordered_map<string, vector<string>>& graph, string start_node, string end_node) {
  // Initialize two queues, one for current layer and other for next layer
  queue<string> current_layer;
  queue<string> next_layer;

  // Initialize a dictionary to store parent node for each node
  unordered_map<string, string> parent_dict;

  // Add the start node to the current layer queue and mark it as visited
  current_layer.push(start_node);
  parent_dict[start_node] = "";

  // Traverse the graph using BFS
  while (!current_layer.empty()) {
    // Get the current node from the current layer queue
    string current_node = current_layer.front();
    current_layer.pop();

    // 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 (const string& neighbor : graph[current_node]) {
      if (parent_dict.count(neighbor) == 0) {
        next_layer.push(neighbor);
        parent_dict[neighbor] = current_node;
      }
    }

    // If the current layer queue is empty, swap the current and next layer queues
    if (current_layer.empty()) {
      swap(current_layer, next_layer);
    }
  }

  // If the end node is not found, return an empty path
  return {};
}

int main() {
  // Define the graph
  unordered_map<string, vector<string>> graph = {
      {"A", {"B", "C"}},
      {"B", {"A", "C", "D"}},
      {"C", {"A", "B", "E", "F"}},
      {"D", {"B"}},
      {"E", {"C"}},
      {"F", {"C"}}
  };

  cout << "Shortest Path Between A and F is:" << endl;
  vector<string> path = find_shortest_path(graph, "A", "F");
  for (const string& node : path) {
    cout << node << " ";
  }
  cout << endl;

  return 0;
}


// Function to find shortest path sequence between start and end node using BFS
function findShortestPath(graph, startNode, endNode) {
  // Initialize two queues, one for current layer and other for next layer
  const currentLayer = [];
  const nextLayer = [];

  // Initialize a dictionary to store parent node for each node
  const parentDict = {};

  // Add the start node to the current layer queue and mark it as visited
  currentLayer.push(startNode);
  parentDict[startNode] = null;

  // Traverse the graph using BFS
  while (currentLayer.length > 0) {
    // Get the current node from the current layer queue
    const currentNode = currentLayer.shift();

    // If the current node is the end node, return the path
    if (currentNode === endNode) {
      return reconstructPath(parentDict, startNode, endNode);
    }

    // Add all the neighbors of the current node to the next layer queue
    for (const neighbor of graph[currentNode]) {
      if (!(neighbor in parentDict)) {
        nextLayer.push(neighbor);
        parentDict[neighbor] = currentNode;
      }
    }

    // If the current layer queue is empty, swap the current and next layer queues
    if (currentLayer.length === 0) {
      [currentLayer, nextLayer] = [nextLayer, currentLayer];
    }
  }

  // If the end node is not found, return null
  return null;
}

// Function to reconstruct the shortest path from the parent dictionary
function reconstructPath(parentDict, startNode, endNode) {
  // Initialize the path list
  const path = [];

  // Start from the end node and follow the parent pointers to the start node
  let currentNode = endNode;
  while (currentNode !== null) {
    path.unshift(currentNode);
    currentNode = parentDict[currentNode];
  }

  return path;
}

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

console.log("Shortest Path Between A and F is:");
console.log(findShortestPath(graph, 'A', 'F'));


import java.util.*;

public class Main {
  // Function to find shortest path sequence between start and end node using BFS
  public static List<String> findShortestPath(Map<String, List<String>> graph, String startNode, String endNode) {
    // Initialize two queues, one for current layer and other for next layer
    Deque<String> currentLayer = new LinkedList<>();
    Deque<String> nextLayer = new LinkedList<>();

    // Initialize a dictionary to store parent node for each node
    Map<String, String> parentDict = new HashMap<>();

    // Add the start node to the current layer queue and mark it as visited
    currentLayer.offer(startNode);
    parentDict.put(startNode, null);

    // Traverse the graph using BFS
    while (!currentLayer.isEmpty()) {
      // Get the current node from the current layer queue
      String currentNode = currentLayer.pollFirst();

      // If the current node is the end node, return the path
      if (currentNode.equals(endNode)) {
        return reconstructPath(parentDict, startNode, endNode);
      }

      // Add all the neighbors of the current node to the next layer queue
      for (String neighbor : graph.get(currentNode)) {
        if (!parentDict.containsKey(neighbor)) {
          nextLayer.offer(neighbor);
          parentDict.put(neighbor, currentNode);
        }
      }

      // If the current layer queue is empty, swap the current and next layer queues
      if (currentLayer.isEmpty()) {
        currentLayer = nextLayer;
        nextLayer = new LinkedList<>();
      }
    }

    // If the end node is not found, return null
    return null;
  }

  // Function to reconstruct the shortest path from the parent dictionary
  private static List<String> reconstructPath(Map<String, String> parentDict, String startNode, String endNode) {
    // Initialize the path list
    List<String> path = new ArrayList<>();

    // Start from the end node and follow the parent pointers to the start node
    String currentNode = endNode;
    while (currentNode != null) {
      path.add(0, currentNode);
      currentNode = parentDict.get(currentNode);
    }

    return path;
  }

  public static void main(String[] args) {
    // Example graph
    Map<String, List<String>> graph = new HashMap<>();
    graph.put("A", Arrays.asList("B", "C"));
    graph.put("B", Arrays.asList("A", "C", "D"));
    graph.put("C", Arrays.asList("A", "B", "E", "F"));
    graph.put("D", Arrays.asList("B"));
    graph.put("E", Arrays.asList("C"));
    graph.put("F", Arrays.asList("C"));

    System.out.println("Shortest Path Between A and F is:");
    System.out.println(findShortestPath(graph, "A", "F"));
  }
}