Does DFS find the shortest path?

No. DFS finds a path between two nodes but not necessarily the shortest one. It explores deeply along each branch, so it may discover a longer path first. For the shortest path in unweighted graphs, use BFS instead.

When should I use DFS pathfinding over BFS?

Use DFS pathfinding when you only need to know if a path exists (not the shortest), when memory is limited (DFS uses less memory than BFS), or when the graph is deep and narrow where DFS can find a path faster.

How does DFS pathfinding work?

DFS pathfinding starts at the source and recursively explores each unvisited neighbor as deeply as possible. If it reaches the destination, it returns the path. If a branch leads to a dead end, it backtracks and tries the next neighbor.

What is the time complexity of DFS pathfinding?

DFS pathfinding runs in O(V + E) time in the worst case, where V is the number of vertices and E is the number of edges. However, it can terminate early if the destination is found before exploring the entire graph.

DFS Pathfinding Visualizer

Visualize how DFS finds a path between two nodes by exploring deeply along each branch. Select a source and destination, then watch DFS navigate through the graph.

Visualize DFS Pathfinding

How It Works

DFS Pathfinding uses Depth-First Search to find a path between a source and destination node. Unlike BFS, DFS does not guarantee the shortest path — it finds the first path it encounters by diving deep into each branch before backtracking.

DFS Pathfinding is useful when any path will do, or when the graph structure favors deep exploration. It uses less memory than BFS since it only needs to store the current path, not all discovered nodes at each level.

1
Start at the source node and mark it as visited
2
If the current node is the destination, the path is found
3
Explore an unvisited neighbor by recursing deeper
4
If the recursive call finds the destination, propagate success back
5
If no unvisited neighbors lead to the destination, backtrack
6
Repeat until a path is found or all reachable nodes are exhausted

Key Properties

Time Complexity

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

Non-Optimal Path

Finds a path but not necessarily the shortest — the result depends on exploration order.

Memory Efficient

Only stores the current path on the stack, using O(V) memory compared to BFS which may store O(V) nodes in the queue.

Backtracking

Naturally backtracks when a dead end is reached, exploring all possible paths systematically.

Common Use Cases

Maze generation — carving paths through a grid using randomized DFS
Reachability testing — checking whether a path exists between two nodes
Constraint satisfaction — exploring solution spaces with backtracking

Frequently Asked Questions

Does DFS find the shortest path?: No. DFS finds a path between two nodes but not necessarily the shortest one. It explores deeply along each branch, so it may discover a longer path first. For the shortest path in unweighted graphs, use BFS instead.
When should I use DFS pathfinding over BFS?: Use DFS pathfinding when you only need to know if a path exists (not the shortest), when memory is limited (DFS uses less memory than BFS), or when the graph is deep and narrow where DFS can find a path faster.
How does DFS pathfinding work?: DFS pathfinding starts at the source and recursively explores each unvisited neighbor as deeply as possible. If it reaches the destination, it returns the path. If a branch leads to a dead end, it backtracks and tries the next neighbor.
What is the time complexity of DFS pathfinding?: DFS pathfinding runs in O(V + E) time in the worst case, where V is the number of vertices and E is the number of edges. However, it can terminate early if the destination is found before exploring the entire graph.

Ready to see it in action?

Open the Visualizer