Three algorithms, three different shapes of graph problem. BFS walks outward in concentric rings. DFS plunges to the bottom and backtracks. Dijkstra walks outward in distance order — like BFS, but with weighted edges. Pick the wrong one and you either get the wrong answer or pay a complexity penalty for nothing.
| Breadth-first search (BFS) | Depth-first search (DFS) | Dijkstra | |
|---|---|---|---|
| Frontier data structure | Queue (FIFO) — collections.deque |
Stack (LIFO) — list, or recursion | Min-heap (priority queue) — heapq |
| Time complexity | O(V + E) |
O(V + E) |
O((V + E) log V) |
| Space complexity | O(V) — frontier can be wide |
O(V) — recursion / stack depth |
O(V) — heap + dist map |
| Edge weights | Unweighted (every edge = 1) | Unweighted (weights ignored) | Non-negative weights only |
| Shortest-path guarantee | Yes — fewest edges | No — finds a path, not the shortest | Yes — minimum weight |
| Visit order | Level-by-level from source | Deep first, then backtrack | Closest unvisited node next |
| Memory pattern | Wide — entire BFS frontier | Narrow — one path's depth | Heap of pending distances |
| Handles negative weights | N/A | N/A | No — use Bellman-Ford or SPFA |
| Handles cycles | Yes (with visited set) | Yes (with visited set) | Yes |
| Iterative or recursive? | Iterative (queue) | Either; recursion is cleaner | Iterative (heap loop) |
Find a path from A to F in this graph. BFS and DFS treat edges as unweighted; Dijkstra uses the weights. Each one tells a different story about the graph.
graph = {
"A": [("B", 1), ("C", 4)],
"B": [("C", 2), ("D", 5)],
"C": [("D", 1)],
"D": [("E", 3), ("F", 10)],
"E": [("F", 1)],
"F": [],
}
# ----- BFS: fewest edges -----
from collections import deque
def bfs_path(graph, start, goal):
parents = {start: None}
q = deque([start])
while q:
u = q.popleft()
if u == goal:
path = []
while u is not None:
path.append(u); u = parents[u]
return path[::-1]
for v, _ in graph[u]:
if v not in parents:
parents[v] = u
q.append(v)
return None
# ----- DFS: any path, not necessarily shortest -----
def dfs_path(graph, start, goal):
visited, stack = set(), [(start, [start])]
while stack:
u, path = stack.pop()
if u == goal:
return path
if u in visited:
continue
visited.add(u)
for v, _ in graph[u]:
if v not in visited:
stack.append((v, path + [v]))
return None
# ----- Dijkstra: minimum total weight -----
import heapq
def dijkstra_path(graph, start, goal):
dist = {start: 0}
parents = {start: None}
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if u == goal:
path = []
while u is not None:
path.append(u); u = parents[u]
return path[::-1], d
if d > dist[u]:
continue
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
parents[v] = u
heapq.heappush(pq, (nd, v))
return None, float("inf")
print(bfs_path(graph, "A", "F")) # ['A', 'C', 'D', 'F'] — 3 edges
print(dfs_path(graph, "A", "F")) # some path (depends on neighbor order)
print(dijkstra_path(graph, "A", "F")) # (['A', 'B', 'C', 'D', 'E', 'F'], 8)Notice the trade-off: BFS finds the path with fewest edges (3 hops, total weight 15 if you compute it). Dijkstra finds the path with minimum total weight (5 hops, weight 8) — longer in hops, cheaper in distance. DFS makes no claim about either; it just finds some reachable path.
BFS and DFS are both O(V + E): every vertex enters and leaves the frontier once, and every edge is examined once. They are tied as the cheapest possible graph traversal — you can't do less than visit each vertex and each edge.
Dijkstra adds a log V factor from the binary heap: each heappush and heappop is O(log V), and across all iterations there are O(V + E) heap operations. With a Fibonacci heap the bound improves to O(E + V log V), but the constant factor wipes out the gain in practice and almost no real-world implementation uses one.
All three are O(V) in the worst case, but the constant differs by problem shape:
d, so BFS holds half the tree near the bottom.if d > dist[u]: continue) or use a decrease-key heap. The simple version is what heapq + the skip-stale pattern gives you.Adjacency-list representations dominate in Python (dict of lists). All three algorithms make pointer-chasing-style accesses, so cache locality is mostly determined by the graph layout, not the algorithm. For dense graphs an adjacency matrix can help BFS/DFS (sequential rows) but hurts Dijkstra (sparse heap operations don't benefit).
BFS, DFS, and Dijkstra are the foundations; most "graph algorithms" you encounter are extensions or hybrids:
O(V+E) shortest path when weights are 0 or 1.h(n) that estimates remaining distance to goal. Same correctness, dramatically prunes the explored space.O(V·E). Detects negative cycles.O(V³). Good when you need every pair on a small graph.If you remember nothing else: BFS for hops, Dijkstra for weights, DFS for structure.
BFS · DFS · Dijkstra · ← Back to Algorithms