Learn
Bellman-Ford Algorithm
The Bellman-Ford Algorithm finds shortest paths from a source vertex while handling negative edge weights. Unlike Dijkstra, it can also detect negative cycles in the graph.
You relax all edges times. After iterations, you've found all shortest paths if no negative cycle exists.
function bellmanFord(edges, n, source):
dist = array of size n, initialized to infinity
dist[source] = 0
for i from 1 to n - 1:
for each edge (u, v, weight):
if dist[u] != infinity and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
for each edge (u, v, weight):
if dist[u] != infinity and dist[u] + weight < dist[v]:
mark v as affected by negative cycle
return dist
Detecting negative cycles: After iterations, any edge that can still be relaxed indicates a negative cycle.