Graph Algorithms Every Developer Should Know: BFS, DFS, and Dijkstra

Three graph algorithms cover most of the graph problems developers meet in practice: breadth-first search (BFS) for shortest paths when every edge costs the same, depth-first search (DFS) for exploring structure such as cycles and connected components, and Dijkstra's algorithm for shortest paths when edges have non-negative weights. If you understand what each one guarantees and when that guarantee breaks, you can handle routing, dependency resolution, social graphs, and grid puzzles with confidence.

What is a graph, and how do you represent one?

A graph is a set of nodes (vertices) connected by edges. Edges can be directed or undirected, and they can carry weights such as distance, latency, or cost. Road maps, package dependencies, service call graphs, and friend networks are all graphs.

Before choosing an algorithm, choose a representation. The two common options are:

• Adjacency list: a map from each node to its neighbors. It uses O(V + E) space and is the default for sparse graphs, which most real graphs are.
• Adjacency matrix: a V × V grid where cell (u, v) marks an edge. It uses O(V²) space but answers "is there an edge from u to v?" in O(1).

Grids are graphs too: each cell is a node and its up, down, left, and right neighbors are edges. You rarely need to build the graph explicitly for a grid.

BFS vs DFS vs Dijkstra at a glance

The key difference is the order in which nodes leave the frontier. BFS takes the oldest node, DFS takes the newest, and Dijkstra takes the cheapest. That single choice determines what each algorithm can prove.

How does breadth-first search work?

BFS explores the graph in layers. It starts at the source, visits all neighbors at distance one, then all nodes at distance two, and so on. Because nodes are processed in the order they were discovered, the first time BFS reaches a node is guaranteed to be along a path with the fewest edges.

When to use BFS

• Shortest path in an unweighted graph or grid, such as the fewest moves in a maze.
• Level-order traversal of a tree.
• Finding everything within k hops, such as "friends of friends".
• Multi-source problems, like spreading from several starting cells at once, by seeding the queue with all sources.

The one rule that prevents most BFS bugs: mark a node as visited when you enqueue it, not when you dequeue it. Otherwise the same node can be added to the queue many times. See the breadth-first search guide for more patterns.

How does depth-first search work?

DFS goes as deep as possible along one branch before backtracking. It can be written recursively or with an explicit stack. DFS does not find shortest paths, but it is ideal for questions about structure.

When to use DFS

• Counting connected components or islands in a grid.
• Detecting cycles, for example circular imports or deadlocked dependencies.
• Topological sorting of a dependency graph, where a node is emitted after all its descendants finish.
• Backtracking searches such as generating paths, permutations, or puzzle solutions.

For cycle detection in a directed graph, track three states per node: unvisited, in progress (on the current path), and done. Reaching an in-progress node means you found a back edge, which means a cycle. The depth-first search guide and topological sort guide show this technique step by step.

One practical caveat: recursive DFS on a graph with a very long path can exceed the language's recursion limit. For large inputs, switch to an explicit stack.

How does Dijkstra's algorithm work?

Dijkstra's algorithm generalizes BFS to weighted edges. It keeps a tentative distance for every node and repeatedly pulls the node with the smallest tentative distance from a min-heap. Once a node is pulled, its distance is final, because every other path to it would have to pass through a node that is already at least as far away. That argument only holds when no edge weight is negative.

Each time a node is finalized, Dijkstra relaxes its outgoing edges: if going through this node gives a neighbor a shorter distance, update the neighbor and push it onto the heap. Using lazy deletion (skipping stale heap entries) keeps the code short and correct.

Code: BFS, DFS, and Dijkstra in Python

from collections import deque
import heapq


def bfs_shortest_hops(graph: dict[str, list[str]], start: str) -> dict[str, int]:
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph.get(node, []):
            if nxt not in dist:  # mark on enqueue
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist


def dfs_reachable(graph: dict[str, list[str]], start: str) -> set[str]:
    seen = {start}
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph.get(node, []):
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return seen


def dijkstra(graph: dict[str, list[tuple[str, int]]], start: str) -> dict[str, int]:
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue  # stale entry
        for nxt, weight in graph.get(node, []):
            candidate = d + weight
            if candidate < dist.get(nxt, float("inf")):
                dist[nxt] = candidate
                heapq.heappush(heap, (candidate, nxt))
    return dist


roads = {
    "A": [("B", 4), ("C", 1)],
    "C": [("B", 2), ("D", 5)],
    "B": [("D", 1)],
}
print(dijkstra(roads, "A"))  # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

In the example, the direct edge A to B costs 4, but going A to C to B costs 3, and Dijkstra finds it. BFS would have reported B as one hop away, which is correct for hop count but wrong for total cost. That is the whole reason to reach for Dijkstra.

Choosing the right graph algorithm

Use this decision sequence when you face a new problem:

1. Is it about shortest paths? If not, DFS is usually the simplest tool for reachability, components, and cycles.
2. Are all edges the same cost? Use BFS.
3. Are edge weights only 0 or 1? A 0-1 BFS with a deque is a neat O(V + E) trick.
4. Are weights non-negative? Use Dijkstra.
5. Can weights be negative? Use Bellman-Ford, which also detects negative cycles.
6. Do you need shortest paths between every pair of nodes on a small graph? Consider Floyd-Warshall.

Other problems have dedicated tools worth knowing by name: union-find for dynamic connectivity, Kruskal's or Prim's algorithm for minimum spanning trees, and topological sort for scheduling with dependencies.

Common graph algorithm mistakes

• Marking nodes visited too late in BFS, causing duplicate work or incorrect distances.
• Using BFS on weighted graphs and assuming the first arrival is the cheapest.
• Running Dijkstra with negative edges, which silently produces wrong answers.
• Forgetting nodes that have no outgoing edges and therefore no key in the adjacency map.
• Missing disconnected components by only starting a traversal from one node.

Key takeaways

• BFS finds shortest paths by edge count; DFS explores structure; Dijkstra finds cheapest paths with non-negative weights.
• The frontier order (oldest, newest, cheapest) is what makes each algorithm correct.
• Mark nodes visited on enqueue in BFS to avoid duplicates.
• Use lazy deletion in Dijkstra: skip heap entries whose distance is stale.
• Negative weights require Bellman-Ford, not Dijkstra.

Frequently asked questions

What is the difference between BFS and DFS?

BFS explores nodes level by level using a queue, so it finds the shortest path in an unweighted graph. DFS follows one branch as deep as it can using a stack or recursion, which makes it well suited to cycle detection, connected components, and topological sorting. Both run in O(V + E) time.

Why does Dijkstra's algorithm not work with negative weights?

Dijkstra finalizes a node as soon as it is removed from the heap, assuming no later path can be cheaper. A negative edge discovered later could make an already-finalized path shorter, breaking that assumption. Bellman-Ford handles negative weights by relaxing all edges repeatedly.

Is BFS or Dijkstra better for shortest paths?

If every edge has the same cost, BFS is simpler and faster at O(V + E). If edges have different non-negative costs, you need Dijkstra, because BFS only minimizes the number of edges, not the total weight.

Which graph algorithms should I learn first for interviews?

Start with BFS and DFS on grids and adjacency lists, since many interview questions reduce to them. Then learn topological sort, Dijkstra, and union-find. Those five cover the large majority of graph questions you are likely to see.