Skip to main content

Shortest Path - Bellman-Ford

Learn Shortest Path - Bellman-Ford (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Bellman-Ford: Shortest Paths with Negative Edges Dijkstra fails when an edge weight is negative . Bellman-Ford handles it by relaxing every edge V-1 times : if dist[u] + w < dist[v] , update dist[v]. A shortest path has at most V-1 edges, so V-1 rounds are enough. One extra round that still improves something proves there is a negative cycle . Cost: O(V ยท E) .

More lessons in Graphs