Graph Algorithms

Traversal and shortest paths: how to walk a graph, and how to choose which traversal fits the question.

Pages in this Section

Breadth-first search (BFS) vs Depth-first search (DFS) vs Dijkstra — 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…
Breadth-first search (BFS) — Breadth-first search explores a graph level by level using a queue. It finds the shortest path in unweighted graphs in O(V + E) and is the foundation of many graph algorithms (web crawling,…
Depth-first search (DFS) — Depth-first search explores as deep as possible before backtracking, using a stack (often the call stack). O(V+E) time. Foundation of cycle detection, topological sort, strongly-connected…
Dijkstra — Dijkstra's algorithm finds shortest paths from a source in a graph with non-negative edge weights. O((V+E) log V) with a binary heap — the standard tool for routing, navigation, and network…