Skip to main content

Shortest Paths and MST Workshop

Retrieval Prompts​

  1. State the decision flow for picking BFS vs Dijkstra vs Bellman-Ford vs Floyd-Warshall.
  2. State Dijkstra's invariant at the moment it extracts a vertex, and where nonnegativity is used.
  3. State why Bellman-Ford needs |V| - 1 passes and what a successful |V|-th pass detects.
  4. Derive the running time of Dijkstra with a binary heap and with a Fibonacci heap.
  5. State the cut property and the cycle property.
  6. Write pseudocode for Kruskal and Prim from memory.

Compare and Distinguish​

  • Dijkstra vs BFS (hint: both maintain frontiers; what is different)
  • Dijkstra vs Prim (same shape, different meaning of key[v])
  • Bellman-Ford vs Floyd-Warshall (SSSP vs APSP, |V||E| vs |V|^3)
  • Kruskal vs Prim (edge-centric global sort vs vertex-centric local grow)
  • minimum spanning tree vs shortest-path tree (these are different objects)
  • O(|E| log |V|) vs O(|E| log |E|) (why the V form is canonical)

Common Mistake Check​

For each statement, identify the error:

  1. "I ran Dijkstra on a graph with a few negative edges; no negative cycle, so the answers are correct."
  2. "Floyd-Warshall is always better for APSP than running Dijkstra many times."
  3. "Prim gives the shortest path tree from the root."
  4. "Kruskal runs in O(|E| log |V|) even without union by rank and path compression."
  5. "Bellman-Ford detects all negative cycles in the graph."
  6. "Dijkstra with a Fibonacci heap is always the fastest choice in practice."

Worked Derivations​

Work these out in writing:

  1. Derive the running time of Dijkstra with a binary heap using lazy deletion: count extract-mins, pushes, and stale-pop skips. Confirm O((|V| + |E|) log |V|).
  2. Derive the running time of Dijkstra with a Fibonacci heap: O(|V|) extract-mins at log |V| amortized, plus O(|E|) decrease-keys at O(1) amortized, so O(|E| + |V| log |V|).
  3. Derive the running time of Floyd-Warshall: three nested loops over |V|, constant work inside, so Theta(|V|^3).

Mini Application​

For each problem, pick the algorithm, run it by hand on the given graph (small enough to fit on paper), and report the answer:

  1. Find shortest distances from s on
s -(3)-> a, s -(5)-> b
a -(2)-> c, b -(1)-> c
c -(4)-> t, a -(6)-> t
  1. Find shortest distances from s on a graph with a negative edge:
s -(5)-> a, s -(2)-> b
a -(-3)-> t, b -(4)-> t
b -(-1)-> a
  1. Find all-pairs distances on the 4-vertex graph from concept 12.
  2. Build an MST on
a-b (2), a-c (3), a-d (3), b-c (4), b-d (4), c-d (5), c-e (1), d-e (6), e-f (3)

Report the MST weight and the edge set.

Implementation Drill​

Pick two of the following and implement them:

  1. Dijkstra with a binary heap (lazy deletion), tested against a trivial O(|V|^2) array-based version.
  2. Bellman-Ford with early exit and negative-cycle detection.
  3. Floyd-Warshall with next[][] path reconstruction.
  4. Kruskal with union-by-rank and path compression.
  5. Prim with a binary heap.

For each, write 5-10 lines comparing its actual runtime against its predicted complexity on a random graph of |V| = 10^3.

Evidence Check​

This practice page is complete only if you can:

  • pick the right shortest-path algorithm for any given (weights, source structure) pair without hesitation
  • trace Dijkstra and Bellman-Ford on a 6-8 vertex graph correctly on paper
  • explain, using the cut property, why Kruskal's next added edge is in some MST
  • defend the running time of each algorithm with a short derivation, not just a quote