Introduction

The right shortest-path algorithm depends on graph structure and edge cost model, not personal preference for DFS or BFS syntax. In unweighted graphs, BFS is the correct baseline for shortest path by edge count. DFS is useful for traversal tasks, but plain DFS does not guarantee shortest path.

Unweighted Graphs: Use BFS

BFS explores nodes layer by layer from the source. The first time a node is reached, BFS has found a path with minimum number of edges from the source.

1from collections import deque
2
3
4def shortest_path_unweighted(graph, start, goal):
5    queue = deque([start])
6    parent = {start: None}
7
8    while queue:
9        node = queue.popleft()
10        if node == goal:
11            break
12
13        for nxt in graph.get(node, []):
14            if nxt not in parent:
15                parent[nxt] = node
16                queue.append(nxt)
17
18    if goal not in parent:
19        return None
20
21    path = []
22    cur = goal
23    while cur is not None:
24        path.append(cur)
25        cur = parent[cur]
26
27    return list(reversed(path))
28
29
30g = {
31    "A": ["B", "C"],
32    "B": ["D"],
33    "C": ["D", "E"],
34    "D": ["F"],
35    "E": ["F"],
36    "F": [],
37}
38
39print(shortest_path_unweighted(g, "A", "F"))

This is the most direct answer when edges are all equal cost.

Why DFS Alone Is Not a Shortest-Path Method

DFS goes deep before exploring siblings. The first found path may be much longer than the shortest one. You can force DFS to enumerate many paths and pick the best, but that is usually expensive and not the standard approach.

DFS remains very useful for:

• Reachability checks.
• Cycle detection.
• Topological ordering in DAG workflows.
• Backtracking and constraint search.

Use DFS for these goals, not as the default shortest path routine.

Weighted Graphs: Use Dijkstra

If edges have non-negative weights, shortest path means minimum total weight, not fewest edges. Dijkstra is the usual baseline.

1import heapq
2
3
4def dijkstra(graph, start, goal):
5    pq = [(0, start)]
6    dist = {start: 0}
7    parent = {start: None}
8
9    while pq:
10        cur_dist, node = heapq.heappop(pq)
11
12        if cur_dist > dist.get(node, float("inf")):
13            continue
14        if node == goal:
15            break
16
17        for nxt, w in graph.get(node, []):
18            nd = cur_dist + w
19            if nd < dist.get(nxt, float("inf")):
20                dist[nxt] = nd
21                parent[nxt] = node
22                heapq.heappush(pq, (nd, nxt))
23
24    if goal not in dist:
25        return None, None
26
27    path = []
28    cur = goal
29    while cur is not None:
30        path.append(cur)
31        cur = parent[cur]
32
33    return dist[goal], list(reversed(path))
34
35
36wg = {
37    "A": [("B", 4), ("C", 1)],
38    "B": [("D", 1)],
39    "C": [("B", 2), ("D", 5)],
40    "D": [],
41}
42
43cost, path = dijkstra(wg, "A", "D")
44print(cost, path)

If negative edges exist, use Bellman-Ford or a different model-specific method.

Should You Use Both DFS and BFS

Sometimes yes, but usually for separate purposes in the same system:

• BFS for shortest path in unweighted navigation.
• DFS for cycle analysis or dependency inspection.

Another related optimization is bidirectional BFS, which runs BFS from source and target in large unweighted graphs. That is still BFS logic, just from both ends.

Complexity and Scaling Notes

With adjacency lists:

• BFS time is O(V + E).
• DFS time is O(V + E).
• Dijkstra with binary heap is around O((V + E) log V).

Complexity alone is not enough. Memory behavior matters:

• BFS can use large memory on wide frontier layers.
• DFS stack is smaller in wide graphs but loses shortest guarantee.

Pick algorithm based on correctness first, then optimize implementation details.

Path Reconstruction Best Practice

Many beginners only compute distance and forget to store predecessors. Real systems often need the actual route for display, simulation, or follow-up actions. Storing parent during traversal is the simplest robust pattern.

Also define behavior for unreachable nodes explicitly, for example returning None or raising a domain-specific exception.

Common Pitfalls

• Using DFS and assuming first-found path is shortest.
• Applying BFS to weighted graphs where edge costs differ.
• Forgetting predecessor tracking when the caller needs actual path.
• Ignoring unreachable-case behavior in API contract.
• Optimizing for speed before proving algorithmic correctness.

Summary

• Use BFS for shortest path in unweighted graphs.
• Use Dijkstra for weighted graphs with non-negative edges.
• Do not use plain DFS as a shortest-path algorithm.
• Use DFS for traversal tasks such as cycles and reachability.
• Define clear return behavior for unreachable targets and path reconstruction.