The Bellman-Ford algorithm solves single-source shortest path problem in a directed graph with **negative** and positive weights. Its time complexity in worst case is equal to Ο(V*E) while Dijkstra’s algorithm has Ο((V+E)log V) time complexity. Thus, if you don’t have negative weights it’s preferable to use Dijkstra’s algorithm.

The only problem that can occur during execution of Bellman-Ford algorithm is a **negative weight cycle**. It is a cycle with weights that sum to a negative number. In that case the algorithm relaxes its nodes indefinitely. Fortunately, Bellman-Ford algorithm can detect negative weight cycle.

The algorithm was discovered independently by Richard Bellman and Lester Ford, Jr.

**Implementation**

The algorithm is based on **relaxation** technique that is also used in Dijkstra’s algorithm. The process of relaxation tests whether the distance going from some vertex **v **through vertex **u **can be improved. If so, the distance is replaced by smallest value.

Let’s have a look at the example. Suppose we have the directed graph below and want to apply Bellman-Ford algorithm to figure out the shortest path from node **A **to** F**.

**Step 1:**

We need to store distance from starting vertex **A** to others. Initially, all vertices have unknown distance (we can use infinity for this) and only vertex **A** has distance 0 (because distance from **A** to **A** is equal to 0).

**Step 2:**

Run relaxation for all edges in the graph. The edges can go in arbitrary order. Suppose, we relax edges in following order:

- A–>B
- E–>F
- A–>C
- B–>D
- C–>E
- D–>F
- B–>E

If so, the result will be following:

- A–>B = 0 + 10 = 10
- E–>F =
**∞** - A–>C = 0 + 20 = 20
- B–>D = 10 + 20 = 30
- C–>E = 20 + 15 = 35
- D–>F = 10 + 20 + 30 = 60
- B–>E = 10 + 15 = 25 (Replace existing distance to vertex E, the previous distance was C->E = 35)

**Step 3:**

In step 3, we again relaxing all vertices in the same order.

- A–>B = 10
- E–>F = 25 + 10 = 35 (Repace current value which is 60)
- A–>C = 20
- B–>D = 30
- C–>E = 35
- D–>F = 60
- B–>E = 25

Voila, the shortest is found and basing on example above we can distinguish following steps of the algorithm:

*Pre-conditions:*

- Graph
**G = (V, E)**. - Array
**D**of size |**V**| for storing distances. - Array
**P**of size |**V**| for storing predecessors. - Starting vertex
**s**.

*Algorithm:*

- Set
**∞**for all elements in**D**. I and many other use max int value to represent infinity. - Set
**D[v]**equal to 0. - Repeate step 3.1 |
**V**|-1 times.- For each edge (
**u**,**v**) ∈**G.E**do step 3.1.1.- If
**D[u]**+ weight of edge**u->v**is less than**D[v]**then set**D[v]**=**D[u]**+ weight of edge**u->v.**And put**P[v]**=**u**.

- If

- For each edge (
- For each edge (
**u**,**v**)**∈****G.E**do step 4.1.- If
**D[u]**+ weight of edge**u->v**is less than**D[v]**then throw exception. Because, graph contains a negative-weight cycle.

- If
- End.

Note: *step 3.1.1 is the relaxation process.*

Here goes Java version of this algorithm on my GitHub repository: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/BellmanFordAlgorithm.java