Four Passes Or One
Bellman-Ford from source 1 on 5 vertices. The edge list is scanned in this fixed order every pass, and the implementation stops early when a pass changes nothing:
| scan position | edge | weight |
|---|---|---|
| 1 | 4→5 | 3 |
| 2 | 3→4 | 2 |
| 3 | 2→3 | 1 |
| 4 | 1→2 | 4 |
What is dist[1..5] immediately after pass 2?
Sign in to answer questions and track your progress
Sign In