Explore advanced graph interview patterns: Dijkstra, Prim's minimum spanning tree, Bellman-Ford with stops, alien dictionary and itineraries. Follow every heap pop and study Python solutions.
The pattern
Advanced Graphs: weights, trees and orders
These problems add costs to the edges. The classic algorithms each answer one question: Dijkstra (cheapest path from one node, with a heap), Bellman-Ford (cheapest path with a limit on edges), Prim or Kruskal (cheapest way to connect everything), and topological sort (an order that respects every rule).
1Dijkstra: the closest is final
With non-negative weights, the closest node not yet finished can't be reached any faster another way. A min-heap hands it over; then its neighbours get a chance at a shorter distance.
2Prim: grow the cheapest tree
To connect everything at the least total cost (a minimum spanning tree), grow one tree and always add the cheapest edge from the tree to a node outside it.
3Bellman-Ford: one more edge per round
Relax every edge, round after round. After round r, each distance is the best using at most r edges, which is exactly what a “within k stops” limit needs.
How to spot which algorithm
- Cheapest / fastest from one source, weights ≥ 0: Dijkstra. If a route's cost is its worst step, use max instead of +.
- “At most k stops” or negative weights: Bellman-Ford, k + 1 rounds.
- Connect everything as cheaply as possible: minimum spanning tree (Prim or Kruskal).
- Recover an order from rules: topological sort. Use every edge once: an Eulerian path.
Reading the pictures
- Edge labels are weights. The blue note beside a node is its best distance so far (≤) or its final one (t =).
- The heap is shown above the picture as a row, smallest first.
- For plain BFS and DFS, see the Graphs patterns page; for Kahn's algorithm, see Topological Sort.
NeetCode 150 · Advanced Graphs
All 6 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Reconstruct Itinerary
HardGiven airline tickets [from, to], build the itinerary that starts at JFK and uses every ticket exactly once. If several are possible, return the one that's smallest in lexical order.
tickets = [[JFK,SFO], [JFK,ATL], [SFO,ATL], [ATL,JFK], [ATL,SFO]]
itinerary so far
tickets (dashed: not used yet)
variables
- tickets used
- 0 of 5
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(E²) typically; exponential in the worst case
- 13 ops
- Brute force
- n/a
Trying every order of the tickets is E! orders. NeetCode's backtracking tries tickets in sorted order and backs up only at dead ends; Hierholzer's algorithm, used here to cross-check the answer, is O(E log E).
“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.
How it works: Reconstruct Itinerary
Step by step
- Current airport / ticket just used
- Tickets used
- Ticket just taken
- Ticket that led to a dead end
Press Start or Step: the step the animation is on lights up below.
- 1
Sort tickets, start at JFK
tickets.sort(); res = ['JFK'] - 2
Use the first unused ticket from here
adj[src].pop(i); res.append(v); if dfs(v): return True - 3
Dead end: put the ticket back
adj[src].insert(i, v); res.pop() - 4
No tickets out, some unused
if src not in adj: return False - 5
All tickets used
if len(res) == len(tickets) + 1: return True
Using every ticket once is a path through every edge of a directed graph (an Eulerian path). Sort each airport's tickets, so trying them in order finds the lexically smallest itinerary first.
NeetCode's approach is backtracking: from the current airport, take the first unused ticket and recurse. If that leaves you stuck with tickets unused, put the ticket back and try the next one. The first time all tickets are used, that's the answer.
Spot it in an interview
- “Use every edge exactly once”: an Eulerian path (Hierholzer's algorithm), or backtracking for small inputs.
- Lexically smallest answer: try choices in sorted order and stop at the first complete one.
Backtracking can undo choices, but sorted order makes dead ends rare. Hierholzer's algorithm is O(E log E).
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.