What does the Bellman-Ford algorithm do?

The Bellman-Ford algorithm is an algorithm for finding the shortest paths from one vertex to all others which, unlike Dijkstra's, works even with negative edge weights.

---

#Idea

It repeatedly "relaxes" (updates) all the edges of the graph until the distances to all vertices stabilize.

"Relaxing an edge" (u → v) with weight w means: if you can reach v through u more cheaply than before, then we update: [ dist[v] = dist[u] + w ]

---

#How it works

1. Set the distance to all vertices = ∞, except the starting one (0).
2. Repeat |V| - 1 times (where |V| is the number of vertices):

• For each edge (u, v, w): if dist[u] + w < dist[v], update dist[v].

3. After that, make one more pass:

• If the distance on some edge can still be reduced, then there is a negative cycle (a path that reduces the distance infinitely).

---

#Example

Let the edges be: A → B (4), A → C (5), B → C (-3)

1. Start: dist[A]=0, dist[B]=∞, dist[C]=∞
2. After iteration 1:

• dist[B] = 4
• dist[C] = 5

3. Relax B→C: dist[C] = 4 + (-3) = 1 → shortest path A → B → C = 1

---

#Complexity

• Time: O(V × E)
• Memory: O(V)

---

#Advantages

• Works with negative weights.
• Can detect negative cycles.

#Disadvantages

• Slower than Dijkstra's algorithm.

---

Summary: The Bellman-Ford algorithm is a universal way to find shortest paths, even if the graph has negative weights, and the only basic algorithm that can detect negative cycles.