Introduction

Finding a path between two nodes sounds simple, but the correct algorithm depends on what path means in your problem. Do you want any path, the shortest path by number of edges, the lowest-cost path in a weighted graph, or every simple path?

Those are different tasks. The fastest way to solve the problem is to choose the algorithm that matches the question instead of reaching for one generic graph traversal every time.

Start by Defining the Goal

Here are the common interpretations:

• Any path in an unweighted graph.
• The shortest path in an unweighted graph.
• The lowest-cost path in a weighted graph.
• All simple paths between two nodes.

If your graph is unweighted and you want the shortest route by number of edges, Breadth-First Search is usually the right answer. If the graph has non-negative edge weights, Dijkstra's algorithm is the standard choice. If you need all simple paths, use backtracking with Depth-First Search.

Breadth-First Search for the Shortest Unweighted Path

BFS explores the graph level by level. The first time it reaches the target, it has found the shortest path in terms of edge count.

1from collections import deque
2
3def shortest_path_bfs(graph, start, goal):
4    queue = deque([(start, [start])])
5    visited = {start}
6
7    while queue:
8        node, path = queue.popleft()
9        if node == goal:
10            return path
11
12        for neighbor in graph.get(node, []):
13            if neighbor not in visited:
14                visited.add(neighbor)
15                queue.append((neighbor, path + [neighbor]))
16
17    return None
18
19graph = {
20    "A": ["B", "C"],
21    "B": ["D"],
22    "C": ["D", "E"],
23    "D": ["F"],
24    "E": ["F"],
25    "F": [],
26}
27
28print(shortest_path_bfs(graph, "A", "F"))

For an unweighted graph, this is usually the best first solution.

Depth-First Search for Any Path or All Paths

DFS is useful when you only need one valid path or when you want to enumerate every simple path.

This version returns all simple paths:

1def all_paths_dfs(graph, start, goal, path=None):
2    if path is None:
3        path = []
4
5    path = path + [start]
6
7    if start == goal:
8        return [path]
9
10    paths = []
11    for neighbor in graph.get(start, []):
12        if neighbor not in path:
13            paths.extend(all_paths_dfs(graph, neighbor, goal, path))
14
15    return paths
16
17graph = {
18    "A": ["B", "C"],
19    "B": ["D", "E"],
20    "C": ["E"],
21    "D": ["F"],
22    "E": ["F"],
23    "F": [],
24}
25
26print(all_paths_dfs(graph, "A", "F"))

This is a good fit for small graphs, but the number of simple paths can explode quickly. In dense graphs, enumerating all paths becomes expensive.

Dijkstra for Weighted Graphs

When edges have costs, BFS is no longer enough. Dijkstra's algorithm finds the lowest total cost path as long as the weights are non-negative.

1import heapq
2
3def dijkstra_path(graph, start, goal):
4    heap = [(0, start, [start])]
5    best_cost = {start: 0}
6
7    while heap:
8        cost, node, path = heapq.heappop(heap)
9        if node == goal:
10            return cost, path
11
12        if cost > best_cost.get(node, float("inf")):
13            continue
14
15        for neighbor, weight in graph.get(node, []):
16            next_cost = cost + weight
17            if next_cost < best_cost.get(neighbor, float("inf")):
18                best_cost[neighbor] = next_cost
19                heapq.heappush(heap, (next_cost, neighbor, path + [neighbor]))
20
21    return None
22
23weighted_graph = {
24    "A": [("B", 2), ("C", 1)],
25    "B": [("D", 5)],
26    "C": [("D", 1), ("E", 4)],
27    "D": [("F", 3)],
28    "E": [("F", 1)],
29    "F": [],
30}
31
32print(dijkstra_path(weighted_graph, "A", "F"))

If the graph can contain negative edge weights, switch to Bellman-Ford instead.

Choosing the Right Representation

Most examples use an adjacency list because it is compact and easy to traverse:

1graph = {
2    "A": ["B", "C"],
3    "B": ["D"],
4    "C": [],
5}

For weighted graphs, store neighbors as (neighbor, weight) pairs. An adjacency matrix is possible, but for sparse graphs it is usually less convenient and more memory-hungry.

Common Pitfalls

The most common mistake is not defining whether you want one path or all paths. Those are very different computational problems.

Another mistake is using DFS when the goal is the shortest path in an unweighted graph. DFS can find a path quickly, but not necessarily the shortest one.

Cycles also cause bugs. If you do not track visited nodes or the current path, a traversal can loop forever. For all paths, check membership in the current path rather than using one global visited set.

Finally, be careful with weighted graphs. BFS ignores weights, so it can return a path with fewer edges but higher total cost.

Summary

• Use BFS for the shortest path in an unweighted graph.
• Use DFS when you want any path or all simple paths.
• Use Dijkstra for lowest-cost paths when edge weights are non-negative.
• Clarify whether the task is one path, shortest path, or all paths before coding.
• Track visited nodes or the current path carefully to avoid infinite loops on cyclic graphs.