Shortest Paths with Negative Weights and Between All Pairs · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

When greedy paths fail

Computing · Algorithms & Data Structures · ages 20-22
Name ______________________   Date ____________

  1. What does Bellman-Ford do instead of locking?

    • It relaxes every edge n minus one times
    • It deletes all edges
    • It guesses one path

  2. Why can Dijkstra return the wrong distance?

    • A negative edge can undercut a locked distance
    • Graphs have too many letters
    • Shortest paths forbid numbers

  3. What does the third Floyd-Warshall index stand for?

    • The paint color
    • Which intermediate vertices are allowed
    • The number of graphs

  4. Dijkstra reports 5 on that graph. Why is it wrong?

    • It locked A before the cheaper path arrived
    • It added wrong
    • Graphs forbid two paths

  5. S to A costs 5, S to B costs 6, B to A costs minus 4. What is the true shortest S to A?

    • 5, the direct edge
    • 6, through B without the last edge
    • 2, through B

  6. An improvement on the last Bellman-Ford pass proves a negative cycle.

    Circle one:   True   False

  7. Floyd-Warshall with no allowed middles compares only direct edges.

    Circle one:   True   False

  8. A friend runs Dijkstra on a graph with a negative edge and trusts the answer. What do you say?

    • Trust it, greedy is always safe
    • Distrust it and run Bellman-Ford, which handles the reducing edge
    • Delete a random vertex
LightMySky · lightmysky.comW1-mt_e8szFezaxO-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

When greedy paths fail W1-mt_e8szFezaxO-s1

  1. It relaxes every edge n minus one times · Repeated relaxation propagates improvements without greedy locks.
  2. A negative edge can undercut a locked distance · Greedy locking never revisits, so later reductions are missed.
  3. Which intermediate vertices are allowed · It grows the set of usable middles step by step.
  4. It locked A before the cheaper path arrived · The lock at 5 ignored the later improvement to 2.
  5. 2, through B · 6 minus 4 is 2, which beats the direct 5.
  6. True · After n minus one passes no honest distance can still improve.
  7. True · With an empty allowed set, only direct edges count.
  8. Distrust it and run Bellman-Ford, which handles the reducing edge · Only the relaxing method stays correct with negative edges.
Worksheet · LightMySky