How does BFS find the shortest path?

BFS explores nodes in order of their distance from the source. Since it visits all nodes at distance d before any node at distance d+1, the first time it reaches the destination is guaranteed to be via the shortest path.

Does BFS pathfinding work on weighted graphs?

No. BFS finds the shortest path only in unweighted graphs where each edge has equal cost. For weighted graphs, use Dijkstra's algorithm, which accounts for varying edge weights using a priority queue.

How is the path reconstructed in BFS?

During traversal, BFS records the parent of each discovered node. Once the destination is reached, the path is reconstructed by following parent pointers backward from destination to source.

What is the difference between BFS traversal and BFS pathfinding?

BFS traversal visits all reachable nodes from a source. BFS pathfinding has a specific destination and stops as soon as it's found, then reconstructs the shortest path using parent pointers.

BFS Pathfinding Visualizer

Visualize how BFS finds the shortest path between two nodes in an unweighted graph. Select a source and destination, then watch BFS discover the optimal route level by level.

Visualize BFS Pathfinding

How It Works

BFS Pathfinding uses Breadth-First Search to find the shortest path between a source and destination node in an unweighted graph. Because BFS explores nodes in order of distance, the first time it reaches the destination is guaranteed to be via the shortest path.

The algorithm tracks the parent of each discovered node, allowing it to reconstruct the path from destination back to source once the target is found.

1
Start at the source node and mark it as visited
2
Add the source node to a queue with no parent
3
Dequeue the front node — if it's the destination, reconstruct the path
4
Visit all unvisited neighbors, recording the current node as their parent
5
Add each newly discovered neighbor to the queue
6
Repeat until the destination is found or the queue is empty

Key Properties

Time Complexity

O(V + E) where V is the number of vertices and E is the number of edges in the graph.

Shortest Path Guarantee

Always finds the path with the fewest edges in an unweighted graph.

Path Reconstruction

Traces back through parent pointers from destination to source to build the shortest path.

Early Termination

Stops as soon as the destination is reached — no need to explore the entire graph.

Common Use Cases

Navigation in grid maps — finding shortest routes in tile-based games
Network hop count — determining minimum hops between routers
Puzzle solving — finding minimum moves in sliding puzzles or Rubik's cube

Frequently Asked Questions

How does BFS find the shortest path?: BFS explores nodes in order of their distance from the source. Since it visits all nodes at distance d before any node at distance d+1, the first time it reaches the destination is guaranteed to be via the shortest path.
Does BFS pathfinding work on weighted graphs?: No. BFS finds the shortest path only in unweighted graphs where each edge has equal cost. For weighted graphs, use Dijkstra's algorithm, which accounts for varying edge weights using a priority queue.
How is the path reconstructed in BFS?: During traversal, BFS records the parent of each discovered node. Once the destination is reached, the path is reconstructed by following parent pointers backward from destination to source.
What is the difference between BFS traversal and BFS pathfinding?: BFS traversal visits all reachable nodes from a source. BFS pathfinding has a specific destination and stops as soon as it's found, then reconstructs the shortest path using parent pointers.

Ready to see it in action?

Open the Visualizer