Skip to main content

Module 3: Graph Algorithms & Network Analysis: Worked Example Studio

Worked examples make graph algorithms concrete. Read these slowly: the important move is the model and precondition check before the algorithm name.

Example 1: When BFS Is the Whole Solution​

Problem statement: A support system has agents connected by handoff relationships. You need the fewest handoffs from Agent A to Agent H in an unweighted graph.

Wrong first attempt: Use Dijkstra because this is a shortest-path problem.

Why it fails: Dijkstra works, but it is unnecessary. There are no edge weights, so every handoff costs exactly one. A priority queue adds complexity without adding correctness.

Correct reasoning: Model agents as vertices and handoff relationships as undirected, unweighted edges. BFS explores vertices in layers: distance 0, then distance 1, then distance 2. The first time BFS reaches H, it has found the minimum number of handoffs.

Final solution sketch:

queue = [A]
dist[A] = 0
parent[A] = null

while queue not empty:
  u = pop_front(queue)
  if u == H: stop
  for each neighbor v of u:
    if v not seen:
      dist[v] = dist[u] + 1
      parent[v] = u
      push_back(queue, v)

Why it works: FIFO order preserves the layer invariant: when a vertex leaves the queue, all shorter paths to it have already been considered.

Transfer question: If some handoffs cost 1 minute and others cost 5 minutes, what breaks? Answer: the equal-cost layer invariant. Use Dijkstra if all weights are nonnegative.

Example 2: Topological Sort Beats "Just Sort the Names"​

Problem statement: A build system has tasks with dependencies. Compile api after models; compile web after api; compile worker after models. Produce a valid build order.

Wrong first attempt: Alphabetically sort the task names: api, models, web, worker.

Why it fails: Alphabetical order ignores dependency edges. api appears before models, violating the graph constraint.

Correct reasoning: Model tasks as vertices and dependencies as directed edges from prerequisite to dependent task:

models -> api
api -> web
models -> worker

This is a DAG if there are no cyclic dependencies. A topological order is any ordering where every edge points forward.

Final solution: One valid order is:

models, api, worker, web

Another valid order is:

models, worker, api, web

Why it works: models appears before both api and worker; api appears before web. Topological sort is about constraints, not unique order.

Transfer question: What if web -> models is added? The graph now has a cycle: models -> api -> web -> models. No valid build order exists.

Example 3: Dijkstra Fails on a Changed Precondition​

Problem statement: Find the cheapest path from S to T.

S -> A cost 2
S -> B cost 5
B -> A cost -10
A -> T cost 2

Wrong first attempt: Run Dijkstra because this is a weighted shortest-path problem.

Why it fails: Dijkstra assumes nonnegative edge weights. It may finalize A with distance 2 before discovering the cheaper path S -> B -> A with cost -5.

Correct reasoning: The graph has a negative edge, so use Bellman-Ford. Relax every edge for |V|-1 rounds and check one more round for negative cycles.

Final distances:

dist[S] = 0
dist[B] = 5
dist[A] = -5
dist[T] = -3

Shortest path:

S -> B -> A -> T

Why it works: Bellman-Ford does not finalize too early. Repeated relaxation allows a later edge to improve an earlier-looking vertex.

Transfer question: If a negative cycle can reach T, what should the algorithm report? Not a finite shortest path; the cost can be driven downward indefinitely.

Completion Standard​

  • You can explain why BFS, topological sort, and Bellman-Ford each fit their example.
  • You can name the hidden precondition that makes each wrong attempt fail.
  • You can create one new worked example for MST or max-flow using the same structure.