Developer/DesignPatterns/AlgorithmsDataStructures/GraphAlgorithms/Fundamentals/graph-traversal-and-shortest-path-algorithms

Graph Traversal and Shortest-Path Algorithms

Concept

A graph is a set of nodes connected by edges, and it's the most general data structure in the DSA canon — a tree is a graph with no cycles, a linked list is a graph where every node has at most one outgoing edge. Two traversal primitives underlie almost everything else: breadth-first search (BFS), which explores level by level using a queue and finds the shortest path (fewest edges) in an unweighted graph, and depth-first search (DFS), which explores as far as possible down one branch before backtracking, using a stack (explicit or via recursion). BFS's level-by-level guarantee is exactly what makes it the right tool for unweighted shortest-path; DFS's natural recursion structure makes it the right tool for cycle detection, topological sort, and connected-component discovery.

Once edges carry weights, unweighted BFS no longer gives shortest paths, and the choice of shortest-path algorithm depends on what the weights can be:

Dijkstra's algorithm — greedily expands the closest unvisited node first (using a priority queue), and is correct as long as all edge weights are non-negative. This is the default for weighted shortest-path in the overwhelmingly common case (road networks, network latency, cost graphs — nothing is usually "negative distance").
Bellman-Ford — relaxes every edge up to V-1 times, tolerating negative edge weights and detecting negative cycles (a cycle whose total weight is negative, which makes "shortest path" undefined since you could loop forever to keep decreasing cost). Strictly more general than Dijkstra, and strictly slower.

A separate, non-traversal structure, union-find (disjoint set), answers connectivity questions efficiently — "are these two nodes in the same component," "would adding this edge create a cycle" — without doing a full traversal per query, which is why it's the standard tool for Kruskal's minimum-spanning-tree algorithm and for online connectivity queries.

Tradeoffs

Algorithm	Handles	Time complexity	When it's the wrong tool
BFS	Unweighted shortest path, level-order traversal	O(V + E)	Any edge has a real weight — BFS ignores it entirely and gives a wrong answer
DFS	Reachability, cycle detection, topological sort, connected components	O(V + E)	Shortest-path questions of any kind — DFS finds a path, not the shortest one
Dijkstra	Weighted shortest path, non-negative weights only	O((V + E) log V) with a binary heap	Any edge weight can be negative — Dijkstra's greedy assumption breaks and it can return a wrong (too-long) answer silently
Bellman-Ford	Weighted shortest path, negative weights allowed; also detects negative cycles	O(V × E)	Non-negative-only graphs where Dijkstra applies — same correctness, strictly worse time complexity for no benefit
Union-Find	Connectivity / cycle-membership queries, without full traversal	~O(α(n)) per operation (effectively constant, with path compression + union by rank)	Anything requiring an actual path, not just "connected or not"

The Dijkstra-vs-Bellman-Ford choice is the sharpest tradeoff in the table: reaching for Bellman-Ford "just to be safe" costs a real asymptotic penalty (O(V×E) vs O((V+E) log V)) for handling a case — negative weights — that most real-world weighted graphs (distances, latencies, costs) never actually have.

When to use / when not to

Use BFS for "shortest path" or "minimum number of steps" questions on unweighted graphs — including graphs where the edges aren't literally physical distance, like "minimum number of API hops between two services" or "fewest word-changes in a word-ladder problem."
Use DFS (or its iterative equivalent with an explicit stack) for topological sort of a DAG — this has a direct real-world tie-in: build-system dependency graphs, CI/CD pipeline stage ordering, and infrastructure-as-code resource ordering are all topological-sort problems, since "build B before A" is exactly a directed edge A→B.
Default to Dijkstra for any weighted shortest-path problem unless the graph is known to have negative edges — reaching for Bellman-Ford unconditionally is a common "playing it safe" habit that costs real performance for a case that essentially never occurs outside specifically constructed problems (e.g., modeling a transaction that yields net value, not just cost).
Use union-find specifically when the question is connectivity-only ("do these become connected," "is there already a cycle") and a full path or distance isn't needed — using a full BFS/DFS traversal per connectivity query when union-find would answer it in near-constant time is a common instance of reaching for a heavier tool than the question requires.

Common pitfall

Using Dijkstra on a graph that turns out to have a negative edge weight without realizing it — Dijkstra doesn't detect this and fail loudly; it silently returns a path that isn't actually shortest, because its greedy "the closest unvisited node is final" invariant depends on non-negative weights to hold. This is a correctness bug, not a performance one, and it's easy to introduce by modeling something as an "edge weight" (e.g., a discount, a rebate, a negative cost representing profit) without checking whether the chosen algorithm actually supports negative values. A second common pitfall: conflating "no cycle in an undirected sense" with "no cycle in a directed sense" when doing cycle detection — DFS-based cycle detection needs to track the current recursion stack (not just visited nodes overall) to correctly detect cycles in a directed graph, since a node visited via one path and revisited via a different, non-recursion-stack path in a directed graph is not necessarily a cycle.

Engineering Lens

Graph problems are where the DSA interview signal is most transferable to real systems, because production dependency structures — service call graphs, build pipelines, data lineage, resource provisioning order — are graphs whether or not anyone modeled them that way explicitly. The strongest answer to "how would you order these deployments" or "how do we detect a circular dependency in this config" is recognizing it as a topological-sort or cycle-detection problem and reaching for the right primitive, not re-deriving graph traversal from scratch under pressure. The Dijkstra/Bellman-Ford choice specifically is a good test of whether an engineer checks their assumptions about the input before picking an algorithm — verifying "can this weight ever be negative" is a five-second check that prevents a silent correctness bug that would otherwise surface only in production, on a specific input, with no obvious symptom pointing back to the algorithm choice.