Skip to content

Volume ITechnology

4.21.0 — Advanced Graphs: The Pattern ​

Recognition cue. The edges have weights. Or the question is "connect everything cheaply", "the cheapest route", or "use every edge exactly once".

Choosing the algorithm ​

This is the whole chapter. Read the question, pick from this table, and the implementation is routine.

the questionthe toolwhy
shortest path, all edges equalBFSfirst arrival is optimal
shortest path, non-negative weightsDijkstraclosest unfinished node can be finalised
shortest path, negative weights or a hop limitBellman-Fordcounts edges in rounds
shortest path between all pairs, small graphFloyd-WarshallO(V^3), three loops
connect everything cheaplyMST — Prim's or Kruskal'sa tree, not a path
use every edge onceHierholzer (Eulerian)linear
use every node onceHamiltonianNP-hard — say so
ordering, dependencies, cycle checktopological sort4.20.8
"are these connected", edges arrivingunion-findincremental

Two distinctions do most of the work.

MST is not shortest path. MST minimises the total cost of connecting everything; shortest path minimises the cost from one source to each node. The path between two nodes in an MST is usually not the shortest path between them.

Eulerian is not Hamiltonian. Every edge once is linear. Every node once is NP-hard. They sound alike and could not be further apart.

Dijkstra, and the one assumption ​

python
import heapq
dist = {}  # (1)
heap = [(0, start)]  # (2)
while heap:
    cost, node = heapq.heappop(heap)  # (3)
    if node in dist: continue          # (4) lazy deletion — stale entry
    dist[node] = cost                  # (5) first pop IS the shortest
    for nei, w in adj[node]:  # (6)
        if nei not in dist:
            heapq.heappush(heap, (cost + w, nei))  # (7)

The template, line by line. (1) dist will hold each node's final shortest distance. (2) A heap of (distance so far, node), smallest first, starting with the source at distance 0. (3) Take the closest node not yet finished. (4) If it is already finished, this entry is out of date, so skip it. (5) The first time a node comes out of the heap, its distance is final. (6) Look at each neighbour (7) and offer it the distance through this node. The heap sorts out which offer is best.

Why finalising is safe: with non-negative weights, any alternative route to the closest unfinished node must pass through another unfinished node, which is already at least as far, and adding a non-negative edge cannot improve it.

That is exactly what negative weights destroy, and it is the answer to the most common follow-up.

Lazy deletion — the if node in dist: continue — exists because a heap cannot update a stored priority. Push duplicates and skip the stale ones.

A common mistake: adding a constant to every weight to remove negatives does not work. It penalises paths with more edges, so the shortest path can change.

The three substitutions worth knowing ​

Dijkstra does not require addition. It requires that extending a path never improves it. So:

  • cost + weight → shortest sum (the usual case)
  • max(cost, weight) → smallest maximum — 4.21.4
  • cost × probability with a max-heap → most likely path

The six problems ​

#ProblemTool
4.21.1Reconstruct ItineraryHierholzer — record on the way out, reverse
4.21.2Min Cost to Connect All PointsMST — Prim's, because the graph is dense
4.21.3Network Delay TimeDijkstra, then take the maximum
4.21.4Swim in Rising WaterDijkstra with max instead of +
4.21.5Alien DictionaryBuild the graph, then topological sort
4.21.6Cheapest Flights Within K StopsBellman-Ford — Dijkstra is wrong here

Prim's or Kruskal's ​

Prim's grows one tree, using a heap of frontier edges. Better on dense graphs, and the only sensible choice when the edges are implicit.

Kruskal's sorts all edges and adds any that join two components, using union-find. Natural when the edges are given explicitly. Stop after n − 1 successful unions.

Both are greedy, and both are justified by the cut property: the cheapest edge crossing any split of the nodes belongs to some minimum spanning tree.

What the interviewer will push on ​

"Why is Dijkstra safe here?" Non-negative weights. Give the finalisation argument.

"What if a weight were negative?" The argument fails; use Bellman-Ford. And no, adding a constant does not fix it.

"Why does Dijkstra fail with a hop limit?" A cheaper route may use too many hops. Either count rounds with Bellman-Ford, or put the hop count into the state.

"MST or shortest path?" Connect everything versus travel from a source. They are different trees.

"Eulerian or Hamiltonian?" Every edge once is linear; every node once is NP-hard.

"What are the duplicate heap entries?" Lazy deletion.

One thing to volunteer: state the assumption your algorithm needs before you write it. "All weights are non-negative, so Dijkstra applies." It answers the next two questions in advance.

Recall

  • MST ≠ shortest path. MST connects everything cheaply; shortest path travels from a source. Different trees.
  • Eulerian (every edge once) is linear. Hamiltonian (every node once) is NP-hard.
  • Dijkstra finalises the closest unfinished node, and that is valid only for non-negative weights.
  • Adding a constant to remove negative weights changes the answer — it penalises longer paths.
  • A hop limit breaks Dijkstra. Use Bellman-Ford, whose rounds count edges, and snapshot the distances each round or several edges chain in one round.
  • Dijkstra works for any cost that never improves when extended: +, max, and multiplying probabilities.
  • Lazy deletion — push duplicates, skip stale pops — because a heap cannot update a priority.
  • Prim's for dense or implicit graphs, Kruskal's for explicit edge lists. Both justified by the cut property. Stop after n − 1 edges.
  • Hierholzer: walk until stuck, record on the way out, reverse at the end.

Next: 4.21.1 Reconstruct Itinerary — the Eulerian path, and the one problem here where getting stuck is not a mistake.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet