Suggest an edit

Improve this article

Refine the answer for “What does the Bellman-Ford algorithm do?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

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**.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts272 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.