Neo & Byte · #2 · Dijkstra and Bellman-Ford
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.
In the VisiGrab app, draw your own graph and step through Dijkstra or Bellman-Ford on it. App Store · Google Play