How to Find the Shortest Path in an Unweighted Graph (BFS)

In an unweighted graph, every edge costs exactly one step. BFS explores the graph level by level, meaning it visits all nodes one step away first, then two steps away, and so on. The first time it reaches the destination, it has taken the shortest possible route.

Create a Queue and add the starting node to it. Create a Visited Set and mark the starting node as visited immediately. Create a Distance Map and set the distance of the starting node to zero.

Start a loop that continues as long as the queue is not empty. In each iteration, dequeue the node at the front of the queue and work with it.

After dequeuing a node, check if it is your destination. If it is, look up its value in the Distance Map and return it. That value is your shortest path length.

If the current node is not the destination, retrieve all its neighboring nodes from the adjacency list or matrix. For each neighbor, check if it has already been visited.

If a neighbor has not been visited, mark it as visited immediately. Set its distance to the current node's distance plus one. Add it to the back of the queue so it gets explored in a future iteration.

If the loop finishes and the queue becomes empty without ever finding the destination, no path exists between the two nodes. Return negative one or infinity to indicate this.