Graph traversals and Dijkstra's algorithm
Implemented BFS, DFS, and Dijkstra's shortest path. Notes on the relationship between graph structure and algorithm choice.
Covered BFS, DFS (both iterative and recursive), and Dijkstra’s shortest path algorithm this week. A few observations worth recording.
BFS vs DFS selection criteria
The textbook framing — BFS for shortest path in unweighted graphs, DFS for exhaustive search — is useful but undersells the practical differences. BFS uses O(V) memory in the worst case (storing the full frontier), while DFS uses O(V) stack depth. For wide, shallow graphs, DFS is more memory-efficient. For deep, narrow graphs, the reverse holds.
In practice, the more relevant question is often whether you need all reachable nodes (DFS is fine) or the nearest node satisfying some condition (BFS is required).
Dijkstra’s implementation detail
The priority queue implementation matters more than I expected. A naive array-scan approach gives O(V²) per extraction. Using a binary heap brings this to O((V + E) log V). For dense graphs where E approaches V², the naive approach can actually be competitive — but for sparse graphs (most real-world networks), the heap-based version is substantially faster.
Next
Topological sort and its applications in dependency resolution. Then moving on to dynamic programming.