λDSA Learning Hubpart of DSA Atlas

Advanced Graph Algorithms

Advanced~4h · 6 lessons10 practice problems

Weighted-graph machinery: Dijkstra, Bellman-Ford, Floyd-Warshall, Prim and Kruskal MSTs — plus a map of SCCs, bridges, and articulation points.

0 of 6 lessons checked off

Introduction

What it is

  • Once edges carry weights, 'shortest' stops meaning fewest edges and BFS stops being enough. This topic covers the four shortest-path/MST algorithms interviews actually ask — Dijkstra, Bellman-Ford, Floyd-Warshall, and Prim/Kruskal — plus recognition-level coverage of SCCs, bridges, and articulation points.

Why it matters

  • Weighted shortest paths and minimum spanning trees are the algorithmic core of routing, logistics, and network design — and 'network delay time' / 'min cost to connect all points' are their interview costumes.
  • The selection logic is the tested skill: non-negative weights → Dijkstra; negatives possible → Bellman-Ford; all pairs on small V → Floyd-Warshall; connect-everything-cheaply → MST.

How it works

  • Dijkstra: greedy settle-the-closest via a min-heap; correct only because non-negative weights mean no later shortcut can appear.
  • Bellman-Ford: relax every edge V−1 times; a V-th improvement betrays a negative cycle.
  • Floyd-Warshall: DP over intermediate vertices — three nested loops, all pairs, O(V³).
  • MST: Kruskal sorts edges and unions non-cycling ones; Prim grows one tree by the cheapest crossing edge. Same answer, different bookkeeping.

Where it's used

  • GPS navigation (Dijkstra/A*), currency-arbitrage detection (Bellman-Ford negative cycles), utility/fiber network layout (MST), compiler SCC condensation, and single-point-of-failure analysis (articulation points).

In interviews

  • Network delay time, cheapest flights within k stops (Bellman-Ford variant), path with minimum effort, min cost to connect all points, critical connections (bridges).
Analogy: Dijkstra is ripples in a pond where thicker water slows the wave — the wavefront always advances at the closest unreached point. An MST is wiring every house with the least copper: connect all, cycle never, cheapest first.

Interactive diagram

The closest unsettled node is settled each round; its edges relax neighbours' tentative distances.

41258310A0B∞C∞D∞E∞
Dijkstra from A

Every node starts at distance ∞ except the source at 0. A min-priority queue always hands us the closest unsettled node — greedy, and correct because edge weights are non-negative.

pq
[(0, A)]

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Dijkstra's algorithm

    Heap-driven greedy settling; lazy deletion; why negatives break it.

    35 min
  2. Bellman-Ford

    V−1 relaxation rounds; negative-cycle detection; k-stops variants.

    25 min
  3. Floyd-Warshall

    All-pairs DP in O(V³); when V ≤ ~400 makes it the easy answer.

    20 min
  4. Minimum spanning trees: Prim & Kruskal

    Cut property; Kruskal = sort + union-find; Prim = heap + grow.

    35 min
  5. Strongly connected components (overview)

    Kosaraju's two passes; Tarjan's low-links; condensation DAGs.

    20 min
  6. Bridges and articulation points (overview)

    Low-link values; edges/vertices whose removal disconnects.

    20 min

Operations

Dijkstra with a min-heap (lazy deletion)

Pop the closest tentative node; if it's stale, skip; otherwise settle it and relax its edges. Non-negative weights make settled distances final.

41258310A0B∞C∞D∞E∞
Dijkstra from A

Every node starts at distance ∞ except the source at 0. A min-priority queue always hands us the closest unsettled node — greedy, and correct because edge weights are non-negative.

pq
[(0, A)]
import heapqdef dijkstra(graph: dict[str, list[tuple[str, int]]], start: str) -> dict[str, int]:    """Shortest distances from start; weights must be >= 0.    O((V + E) log V) with a binary heap."""    dist: dict[str, int] = {start: 0}    heap: list[tuple[int, str]] = [(0, start)]    settled: set[str] = set()    while heap:        d, node = heapq.heappop(heap)        if node in settled:              # stale entry — lazy deletion            continue        settled.add(node)        for neighbour, weight in graph[node]:            candidate = d + weight            if candidate < dist.get(neighbour, float("inf")):                dist[neighbour] = candidate                heapq.heappush(heap, (candidate, neighbour))    return dist
Time: O((V + E) log V)Space: O(V + E)

Edge cases

  • Unreachable nodes simply never enter dist.
  • Duplicate heap entries are expected — the settled check discards stale ones (heapq has no decrease-key).
  • ONE negative edge voids the correctness proof — switch algorithms, don't patch.

Common mistakes

  • Skipping the settled/stale check, reprocessing nodes with outdated distances.
  • Running it on negative weights because 'it usually works' — it silently doesn't.
  • Pushing (node, dist) instead of (dist, node) — the heap must order by distance.

Bellman-Ford (negatives allowed, cycles detected)

Relax all E edges, V−1 times: round i finalises all shortest paths using ≤ i edges. A V-th round that still improves proves a negative cycle.

Bellman-Ford (negatives allowed, cycles detected)
def bellman_ford(    n: int, edges: list[tuple[int, int, int]], start: int) -> list[float] | None:    """Shortest dists from start; None if a negative cycle is reachable.    edges = [(u, v, w), ...]. O(V · E)."""    dist: list[float] = [float("inf")] * n    dist[start] = 0    for _ in range(n - 1):               # paths use at most n-1 edges        changed = False        for u, v, w in edges:            if dist[u] + w < dist[v]:                dist[v] = dist[u] + w                changed = True        if not changed:                  # early convergence            break    for u, v, w in edges:                # one extra round: still improving?        if dist[u] + w < dist[v]:            return None                  # negative cycle reachable    return dist
Time: O(V · E) — the price of tolerating negativesSpace: O(V)

Edge cases

  • Negative EDGES are fine; negative CYCLES make 'shortest' undefined — hence the None.
  • Capping rounds at k+1 answers 'cheapest path with ≤ k stops' (with per-round snapshots).
  • float('inf') + w overflow isn't a thing in Python — but guard dist[u] != inf in other languages.

Common mistakes

  • Confusing negative edges (handled) with negative cycles (detected, not solved).
  • Relaxing fewer than V−1 rounds without the early-exit check.

Kruskal's MST (sort + union-find)

Take edges cheapest-first; keep any edge joining two different components (union succeeds), skip cycle-closers. Stop at V−1 edges.

Kruskal's MST (sort + union-find)
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> int | None:    """Total MST weight over vertices 0..n-1, or None if disconnected.    edges = [(w, u, v), ...]. O(E log E)."""    parent = list(range(n))    def find(x: int) -> int:        while parent[x] != x:            parent[x] = parent[parent[x]]    # compression (halving)            x = parent[x]        return x    total = used = 0    for w, u, v in sorted(edges):            # cheapest edge first        ru, rv = find(u), find(v)        if ru == rv:            continue                          # would close a cycle        parent[ru] = rv        total += w        used += 1        if used == n - 1:                     # tree complete            return total    return None                               # graph wasn't connected
Time: O(E log E) for the sort; unions are ~O(1)Space: O(V)

Edge cases

  • Disconnected graphs have no spanning tree — the used < n−1 fall-through.
  • Equal weights: any tie order yields A valid MST (weights unique ⇒ MST unique).
  • Prim (heap-grown) wins on dense graphs given adjacency lists; same total.

Common mistakes

  • Forgetting the cycle skip — the whole point of union-find here.
  • Stopping at n edges instead of n−1 (a tree on n vertices has n−1 edges).

Complexity analysis

OperationBestAverageWorstSpace
BFS (unweighted shortest path)O(V+E)O(V+E)O(V+E)O(V)
Dijkstra (binary heap)O((V+E) log V)O((V+E) log V)O((V+E) log V)O(V+E)
Bellman-FordO(E) early-exitO(V·E)O(V·E)O(V)
Floyd-Warshall (all pairs)O(V³)O(V³)O(V³)O(V²)
Kruskal MSTO(E log E)O(E log E)O(E log E)O(V)
Prim MST (heap)O(E log V)O(E log V)O(E log V)O(V+E)

The selection table: unweighted → BFS; non-negative → Dijkstra; negatives → Bellman-Ford; all pairs & small V → Floyd-Warshall; connect-all → MST.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Floyd-Warshall: all-pairs shortest paths in twelve lines
def floyd_warshall(n: int, edges: list[tuple[int, int, int]]) -> list[list[float]]:    """dist[i][j] = shortest path cost for ALL pairs. O(V^3) time, O(V^2) space.    Handles negative edges (not negative cycles: dist[i][i] < 0 reveals one)."""    INF = float("inf")    dist = [[INF] * n for _ in range(n)]    for i in range(n):        dist[i][i] = 0    for u, v, w in edges:        dist[u][v] = min(dist[u][v], w)      # keep parallel-edge minimum    # k = largest intermediate vertex allowed — the DP dimension    for k in range(n):        for i in range(n):            dik = dist[i][k]            if dik == INF:                continue            for j in range(n):                candidate = dik + dist[k][j]

What interviewers expect you to know

What interviewers expect you to know

  • The selection table cold — most 'advanced graph' questions are really 'pick the right algorithm and justify it'.
  • WHY Dijkstra needs non-negative weights: settling assumes no future edge can shorten a settled node; a negative edge breaks that promise.
  • The MST cut property: the cheapest edge crossing any partition belongs to some MST — it's why both greedy MSTs are correct.
  • Bellman-Ford's extra round as negative-cycle detector (arbitrage questions in disguise).

Recognition-level topics (name, don't derive)

  • SCCs: Kosaraju = DFS, transpose, DFS in reverse finish order; Tarjan = one pass with low-links. Condensing SCCs yields a DAG.
  • Bridges/articulation points: DFS low-link values; 'critical connections' = bridges. Removal disconnects the graph.
  • A*: Dijkstra + admissible heuristic — the games/maps answer.

How to answer selection questions

  • Interrogate the input aloud: 'Weighted? Negative? One source or all? Dense or sparse?' — then name the algorithm AND its complexity in the same sentence.
  • For MST vs shortest path confusion: shortest path optimises per-destination routes; MST optimises total wiring. Different objectives, different trees.

Common mistakes

Dijkstra with negative edges

No error is raised — answers are just wrong. Negative anything → Bellman-Ford (or reweighting via Johnson's, as a name-drop).

Missing the stale-entry check

heapq can't decrease-key, so duplicates accumulate; processing a stale pop corrupts distances. `if node in settled: continue` is mandatory.

Floyd-Warshall loop order

k must be the OUTER loop. i-j-k order produces plausible-looking wrong matrices — the sneakiest bug on this page.

MST when the ask was shortest path

'Cheapest way to connect all offices' = MST; 'cheapest route from HQ to each office' = Dijkstra. Read for total-cost vs per-path.

Kruskal without the cycle skip

Sorting edges is half the algorithm; refusing same-root unions is the other half.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Medium (6)

Hard (4)

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Scenario1. Flight prices between cities (all positive), one origin, need cheapest cost to every city. Algorithm?
  2. Concept2. Why does one negative edge break Dijkstra?
  3. Code output3. Kruskal on edges (w,u,v): (1,A,B), (2,B,C), (3,A,C), (4,C,D). Which edges form the MST, and what's the total?
  4. Scenario4. Currency exchange rates as a graph (edge = −log(rate)); you must detect a profitable cycle. Tool?
  5. Complexity5. V = 300 cities, dense roads, and you need shortest paths between ALL pairs. Cheapest correct approach?
0 of 5 answered

Frequently asked questions

Do I need Tarjan's SCC or bridge-finding by heart?

For most loops: recognition level — know what SCCs/bridges are, that low-link DFS finds them in O(V+E), and when a question ('critical connections') is asking for them. Full implementations are specialist/competitive territory.

Prim or Kruskal — which should I default to?

Kruskal if you already have an edge list and a union-find (less code, easier to prove). Prim with a heap when handed adjacency lists or when the graph is dense. Same tree cost either way — say that.

Where does A* fit relative to Dijkstra?

A* = Dijkstra ordered by dist + heuristic(node). With an admissible (never-overestimating) heuristic it's exact but explores far less — the games/maps standard. Interviews want the one-sentence relationship, rarely an implementation.

Summary & cheat sheet

Key takeaways

  • Selection is the skill: BFS → Dijkstra → Bellman-Ford → Floyd-Warshall as weights/negatives/all-pairs enter; MST for connect-everything.
  • Dijkstra = heap + settle-closest + stale-skip; valid only ≥ 0 weights.
  • Bellman-Ford = V−1 relaxation rounds; round V detects negative cycles.
  • Floyd-Warshall = k-outermost DP; V ≤ 400 rule of thumb.
  • MST correctness = the cut property; Kruskal rides union-find.

Formulas & cheat sheet

  • Dijkstra: O((V+E) log V) · Bellman-Ford: O(VE) · Floyd-Warshall: O(V³)
  • MST edges = V − 1; cut property justifies greedy
  • Arbitrage: profit cycle ⇔ negative cycle under −log weights

Interview checklist

  • I can implement Dijkstra with lazy deletion from memory.
  • I can state why negative weights break it — and what replaces it.
  • I can write Kruskal with union-find and the V−1 stop.
  • I can pick the right algorithm from constraints alone.