Shortest Paths

Dijkstra, Bellman-Ford and negative cycles, Floyd-Warshall, and choosing between them.

0 / 6 solved

Question Tags Difficulty Success

1. Bad Toll Road

Algorithms

Easy 77%

2. Four Passes Or One

bellman-fordrelaxation +2

Medium —

3. The Rebate Edge

dijkstranegative-weights +2

Medium —

4. Three Ways To Break

dijkstrainteger-overflow +2

Medium —

5. Loops In Wrong Order

floyd-warshallall-pairs-shortest-path +2

Hard —

6. Correct But Exponential

dijkstralazy-deletion +2

Hard —

Learning Resources

cp-algorithms, Dijkstra's algorithm

cp-algorithms, Bellman-Ford

cp-algorithms, Floyd-Warshall

Jeff Erickson, Single-Source Shortest Paths chapter

MIT 6.006 Lecture 13, Dijkstra's algorithm

Up next

6 of 6 questions here are still unsolved.

Next module Minimum Spanning Trees