Which algorithm for finding single-source shortest paths can handle negative edge weights (but not negative cycles)?
Show answer
Bellman-Ford algorithm
Unlike Dijkstra's algorithm, Bellman-Ford relaxes all edges |V|-1 times. It can also be used to detect the presence of negative cycles by checking if any edge can be further relaxed after the final iteration.
Also asked as:
- Which classic single-source shortest-path algorithm can process negative edge weights and detect a reachable negative-weight cycle?