Neo & Byte · #2 · Dijkstra and Bellman-Ford

Final Answer

Four-panel comic. Dijkstra stamps the shortest path to B as 2, final. Byte finds a path through a −3 edge that costs 1, Dijkstra refuses to look back, and Bellman-Ford, checking every edge, gets 1.

Transcript

  1. Panel 1. Dijkstra: “Shortest path to B: 2. Final.”
  2. Panel 2. Byte: “A to C is 4, and this coupon takes off 3. That's 1!”
  3. Panel 3. Dijkstra: “B is stamped. I don't go back.”
  4. Panel 4. Bellman-Ford: “I check every edge, V − 1 times. Slow, but never sure too early.”

Actually…

Dijkstra's algorithm treats a vertex's distance as final once it takes that vertex from the queue, which is only safe when no edge weighs less than zero. Here it settles B at 2 before it ever reaches C, so the path through C's −3 edge, which weighs 1, comes too late. Bellman-Ford relaxes every edge in V − 1 rounds, so negative weights are fine, and one more round reveals a negative cycle reachable from the start.

See it step by step

In the VisiGrab app, draw your own graph and step through Dijkstra or Bellman-Ford on it. App Store · Google Play