DSA Roadmap/Graphs

Shortest Paths (Dijkstra, Bellman-Ford, Floyd-Warshall)

Three algorithms plus Senior compositions: Dijkstra / Bellman-Ford / Floyd-Warshall for classical weights, then path counts and min-bottleneck paths (binary search + BFS or Dijkstra on max edge).

!!4/5Theory: 2h 40m7 problems

From unweighted to weighted: why BFS isn't enough anymore

BFS finds shortest paths in unweighted graphs by exploring in strict distance order — every edge "costs" 1, so the first time you reach a node is necessarily via the fewest edges. The moment edges have different weights, that guarantee breaks: a path with more edges can easily have a smaller total weight than a path with fewer edges. You need algorithms that reason about cumulative edge weight rather than edge count. This subtopic covers the three that matter for interviews, each suited to a different constraint on the graph.

Dijkstra's algorithm — non-negative weights, single source

The idea: maintain a running best-known distance to every vertex (initialized to ∞, except the source at 0), and repeatedly select the unfinalized vertex with the smallest known distance, "finalize" it, and relax all of its outgoing edges (i.e., check whether going through this vertex improves the distance to its neighbors). A min-heap makes "find the smallest unfinalized distance" efficient.

import heapq def dijkstra(n, graph, source): # graph[u] = list of (v, weight) dist = [float('inf')] * n dist[source] = 0 heap = [(0, source)] visited = set() while heap: d, u = heapq.heappop(heap) if u in visited: continue # stale heap entry — a shorter path already finalized u visited.add(u) for v, weight in graph[u]: if d + weight < dist[v]: dist[v] = d + weight heapq.heappush(heap, (dist[v], v)) return dist

Why negative weights break it — the argument to state explicitly: Dijkstra's correctness relies on a greedy claim: once a vertex is popped from the heap with the smallest current distance, that distance is final and can never be improved later. This is only true if every edge weight is non-negative — because if all remaining edges add non-negative weight, no future path through an unfinalized (necessarily-larger-or-equal-distance) vertex could possibly produce a smaller distance to the vertex you just finalized. A negative edge shatters this: a longer, seemingly-worse path could later take a negative-weight shortcut and undercut a distance you already "locked in" and will never revisit. Dijkstra has no mechanism to revisit a finalized vertex, so it produces a wrong, no-error, silently-incorrect answer on graphs with negative edges — this is the single most important fact to say out loud about Dijkstra in an interview.

Bellman-Ford — handles negative weights, detects negative cycles

The idea: instead of greedily finalizing vertices, simply relax every edge in the graph, and repeat this for V - 1 rounds. Why V - 1? Because the longest possible simple shortest path (no repeated vertices) has at most V - 1 edges, and each full round of relaxation is guaranteed to correctly extend the shortest-path prefix by at least one more edge for every vertex.

def bellman_ford(n, edges, source): # edges = list of (u, v, weight) dist = [float('inf')] * n dist[source] = 0 for _ in range(n - 1): updated = False for u, v, weight in edges: if dist[u] != float('inf') and dist[u] + weight < dist[v]: dist[v] = dist[u] + weight updated = True if not updated: break # optimization: stop early if nothing changed this round # One more round: if anything still improves, a negative cycle is reachable from source for u, v, weight in edges: if dist[u] != float('inf') and dist[u] + weight < dist[v]: return None # negative cycle detected return dist

The extra V-th round is the negative-cycle detector: if a valid shortest path can have at most V - 1 edges, then any further improvement after V - 1 full rounds means you're riding a cycle that keeps reducing the "distance," which is only possible if that cycle has negative total weight. This is a distinct and important skill from just computing distances — many interview questions specifically ask you to detect whether a negative cycle exists (e.g., in currency-arbitrage-style problems), not just compute shortest paths assuming one doesn't.

Floyd-Warshall — all pairs at once, O(V³)

The idea: dynamic programming over an increasing set of allowed intermediate vertices. Define dist[i][j] as the shortest path from i to j using only vertices {1, ..., k} as intermediates; at each step k, ask whether routing through vertex k improves any pair: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

def floyd_warshall(n, edges): INF = float('inf') dist = [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] = 0 for u, v, weight in edges: dist[u][v] = min(dist[u][v], weight) # keep the smaller if there are multi-edges for k in range(n): for i in range(n): if dist[i][k] == INF: continue # skip: no path through k helps from i for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist # dist[i][i] < 0 for some i implies a negative cycle

Reach for Floyd-Warshall specifically when you need every pair's shortest distance and V is small (roughly V ≤ 400–500, since it's O(V³)) — running Dijkstra from every vertex costs O(V · E log V), which can actually be worse than O(V³) on dense graphs, and Floyd-Warshall's implementation is dramatically simpler (three nested loops, no heap). It also handles negative edge weights (though not negative cycles reachable in a way that makes distances undefined — those show up as a negative value on the diagonal, dist[i][i] < 0).

Decision table: which algorithm, when

SituationAlgorithmWhy
Single source, all edge weights ≥ 0DijkstraFastest option for this common case: O((V + E) log V) with a binary heap
Single source, some edge weights < 0Bellman-FordDijkstra's greedy finalization is provably wrong here
Need to detect a negative cycleBellman-FordThe extra V-th relaxation round is a direct negative-cycle test
Need shortest paths between every pair of verticesFloyd-Warshall (small V) or Dijkstra from every vertex (sparse, larger V, non-negative weights)Floyd-Warshall is O(V³) and trivial to implement; repeated Dijkstra is O(V·E log V), better when the graph is sparse
Unweighted graph (or all edges cost 1)Plain BFSDijkstra with unit weights reduces to BFS but with unnecessary O(log V) heap overhead
Edge weights are only 0 or 10-1 BFS (deque, push 0-weight to front)O(V + E), avoids the heap entirely — a specialized trick worth knowing exists, even if it's less commonly required in interviews
"At most k stops/edges" constraintBellman-Ford-style, capped at k rounds (or BFS/Dijkstra over an expanded (node, stops_used) state space)Dijkstra's standard form has no notion of "steps used," so the state needs augmenting
Unit-cost moves on an invented state (locks, word transforms, keys on a grid)BFS / bidirectional BFS on the state graph — see State-space & Implicit Graph BFSSame shortest-path idea; the modeling work is defining the vertex, not picking Dijkstra

Senior composition patterns

Two variants show up constantly once the textbook algorithms are solid:

Counting shortest paths. Run Dijkstra (or BFS if unweighted) as usual, but keep a parallel ways[v] array: when you find a strictly better distance to v, set ways[v] = ways[u]; when you find an equal distance, add ways[u] into ways[v] (mod 10⁹+7 if required). Do not finalize a node in a way that drops equal-cost arrivals — the stale-entry skip still applies for worse distances, but equal distances must still contribute to the count.

Minimize the bottleneck (max edge on the path), not the sum. Classic prompt: "swim when the water level is at least the max height on your path — minimize that level." Two equivalent approaches:

  1. Dijkstra keyed on bottleneck — heap priority is max(cost_so_far, grid[nr][nc]) instead of cost_so_far + weight. First time you pop the destination, that bottleneck is optimal.
  2. Binary search on the answer + BFS — guess level mid; BFS only through cells ≤ mid; search the minimum feasible mid.

Both are O(V log V + E log V) or O(E log W) respectively; saying both options is a strong Senior signal. This is not an MST problem even when it appears next to spanning-tree drills — you need a path from A to B with a min-max objective, not a global connector of all vertices.

Complexity, precisely

AlgorithmTimeSpace
Dijkstra (binary heap)O((V + E) log V)O(V + E)
Dijkstra (no heap, dense graph)O(V²)O(V)
Bellman-FordO(V · E)O(V)
Floyd-WarshallO(V³)O(V²)

The heap-based Dijkstra bound comes from: each vertex is popped once (O(V log V)), and each edge can trigger at most one heap push (O(E log V)) — dominating for typical sparse graphs where E is the larger term. Bellman-Ford's O(VE) comes directly from V - 1 rounds, each doing O(E) work relaxing every edge.

Pitfalls and interview gotchas

  • Using Dijkstra on a graph with negative weights and getting a wrong answer with no error. This is the single most tested conceptual gotcha in this subtopic — always ask about the sign of edge weights before choosing an algorithm.
  • Forgetting the "stale heap entry" check in Dijkstra. Because you can push a vertex to the heap multiple times before it's finalized (once per improving relaxation), you must skip a popped vertex if it's already been visited/finalized — otherwise you redo work and, worse, can corrupt results in variants that track path counts or additional state.
  • Off-by-one on Bellman-Ford's round count. It's V - 1 rounds to guarantee correctness, plus one extra round specifically to detect negative cycles — conflating these two (e.g., stopping after V - 1 rounds and assuming "no more updates possible" without the extra check) misses cycle detection entirely.
  • Floyd-Warshall's loop order matters. k must be the outermost loop, not i or j — the DP invariant ("using only intermediates from {1..k}") is only valid if you fully complete each k before moving to the next. Swapping loop order silently produces incorrect results without any error.
  • Disconnected graphs / unreachable vertices. Represent "no path yet" as infinity consistently, and guard against infinity-plus-weight overflowing into a false "improvement" (if dist[u] != INF and ... — skip the check entirely rather than let INF + weight wrap or compare incorrectly).
  • Self-loops and multi-edges with weights. A self-loop with positive weight is irrelevant (never helps); with negative weight, it's itself a negative cycle. Multiple edges between the same pair of nodes just need "keep the minimum weight" when building your representation — don't silently overwrite with the last one seen.
  • Confusing shortest path with minimum spanning tree. They sound similar and both commonly use a heap, but they optimize different things: shortest path minimizes total weight from one source to each destination independently, while MST (Advanced Niche Algorithms) minimizes the total weight to connect all vertices together. Dijkstra and Prim's are structurally nearly identical algorithms (grow a frontier via a min-heap) but their priority key differs: Dijkstra keys on cumulative distance from source, Prim's keys on the single edge weight crossing into the frontier. Min-bottleneck path problems (Swim in Rising Water) are still shortest-path variants — not MST.

Where this reappears

The heap mechanics here are exactly the ones from Heap Fundamentals & Top-K Pattern — if Dijkstra's use of a min-heap feels unfamiliar, that's the prerequisite to revisit. Prim's algorithm (Minimum Spanning Tree, in Advanced Niche Algorithms) reuses this same frontier-expansion-via-heap skeleton with one small but consequential change to the priority key, which is the cleanest way to see the shortest-path/spanning-tree distinction concretely. When the "graph" is something you invent (password dials, bus rides, key bitmasks), start from State-space & Implicit Graph BFS and only upgrade to a heap when transition costs stop being uniform.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.