The foundation of the Bellman-Ford algorithm is dynamic programming. It relaxes each edge to determine the shortest pathways step-by-step. Comparing and updating the shortest path estimate if a shorter path is discovered is the process known as relaxation. The method checks every edge and attempts to improve the shortest path estimate throughout each iteration. Here are the step-by-step workings of the Bellman-Ford algorithm:

**Step 1: Initialisation**

Set the distance from the source vertex to itself as 0, and to all other vertices as infinity.

for each vertex v in Graph:

if v == source:

distance[v] = 0

else:

distance[v] = ∞

**Step 2: Relaxing the edges**

For each edge, if the distance to the destination vertex can be shortened by going through the source vertex, update the destination’s distance.

for i from 1 to |V|-1:

for each edge (u, v) in Graph:

if distance[u] + weight(u, v) < distance[v]:

distance[v] = distance[u] + weight(u, v)

**Step 3: Check for Negative Cycles**

Repeat the relaxation step V−1 times for each edge in the graph, where V is the number of vertices. Complete one more relaxing step following V−1 iterations. A negative weight cycle exists if any distance is updated.

for each edge (u, v) in Graph:

if distance[u] + weight(u, v) < distance[v]:

print “Graph contains a negative-weight cycle”

return

**Step 4: Shortest paths**

The final step is to return the shortest path. If there are no negative cycles in the graph, the shortest path from the source node to all other nodes of the graph is returned.

return distance

### How does Bellman-Ford Algorithm Handle Negative Weight Edges & Cycles?

Bellman-Ford algorithm has a key strength in handling the negative weight edges and cycles in the graph. Let’s see how it handles both:

Negative weight edges can be present in graphs if the existence of certain transitions or paths would mean a decrease in cost (or distance) from what has already been computed. The Bellman-Ford correctly computes the shortest path even when such edges exist by allowing for multiple relaxations of edges.

A negative weight cycle is when a cycle in the graph has a total sum of weights that is negative. In this situation, no shortest path will exist because the algorithm could keep reducing the path cost by travelling around the cycle indefinitely.

- If after V−1 relaxations no edges can be relaxed and some can still be relaxed, then a negative weight cycle is present.
- The Bellman-Ford algorithm discovers this and indicates the presence of negative weight cycles by returning a special value to the user so that it should be thought of as a way of warning that, in such cases, the shortest path cannot be computed in a well-defined way.

### Pseudocode of Bellman-Ford Algorithm

Here is the pseudocode for the bellman-ford algorithm:

function BellmanFord(Graph, source):

// **Step 1:** Initialise distances

for each vertex v in Graph:

if v == source:

distance[v] = 0

else:

distance[v] = ∞

// **Step 2: **Relax edges |V|-1 times

for i from 1 to |V|-1:

for each edge (u, v) in Graph:

if distance[u] + weight(u, v) < distance[v]:

distance[v] = distance[u] + weight(u, v)

// **Step 3: **Check for negative-weight cycles

for each edge (u, v) in Graph:

if distance[u] + weight(u, v) < distance[v]:

print “Graph contains a negative-weight cycle”

return

// Shortest Path

return distance

**Explanation:**

**Initialisation**: The distance to the source is set to 0, and all other distances are initialised to infinity.
**Relaxation**: For each edge, check if a shorter path can be found. If so, update the shortest path estimate.
**Negative Cycle Check**: After relaxing the edges V−1 times, check once more for negative-weight cycles.

### Bellman-Ford Algorithm Example

For this example, consider a graph with 5 vertices (A, B, C, D, E) with the following edges having weights:

A -> B (weight 2)

A -> C (weight 3)

B -> D (weight 1)

C -> D (weight 6)

B -> E (weight 4)

D -> E (weight -1)

From the given graph weights, we will run the Bellman-Ford algorithm to determine the shortest path from vertex (node) A to all other vertices (nodes).

**Step 1: Initialisation**

The first step is to initialise all other vertices’ distances to infinity (∞) and the distance to the source vertex A to 0. We also keep track of the parent of each vertex (used to reconstruct paths).

**Vertex** |
**Distance from A** |
**Parent** |

A |
0 |
– |

B |
∞ |
– |

C |
∞ |
– |

D |
∞ |
– |

E |
∞ |
– |

**Step 2: Relaxing the edges**

In this step, we try to discover the shortest path to each vertex by relaxing each edge in the graph. V is the number of vertices, and we repeat this method V−1 times. This makes sure we take into consideration all potential shortest paths.

**Iteration 1:**

- A -> B (distance(B) = min(∞, 0 + 2) = 2
- A -> C (distance(C) = min(∞, 0 + 3) = 3
- B -> D (distance(D) = min(∞, 2 + 1) = 3
- C -> D (distance(D) = min(3, 3 + 6) = 3 (no change)
- B -> E (distance(E) = min(∞, 2 + 4) = 6
- D -> E (distance(E) = min(6, 3 + (-1)) = 2

**Vertex** |
**Distance from A** |
**Parent** |

A |
0 |
– |

B |
2 |
A |

C |
3 |
A |

D |
3 |
B |

E |
2 |
D |

**Iteration 2:**

- A -> B (distance(B) = 2), no change
- A -> C (distance(C) = 3), no change
- B -> D (distance(D) = 2), no change
- C -> D (distance(D) = 3), no change
- B -> E (distance(E) = 2), no change
- D -> E (distance(E) = 2), no change

**Iteration 3: **All distances are unchanged after the third iteration of the algorithm.

**Iteration 4: **All distances are unchanged after the fourth iteration of the algorithm.

**Step 3: Checking negative cycles**

We now check the graph to see if there are any negative weight cycles following the V−1 iterations. To do this, try to relax each edge only once more. If any distance can be reduced further, it means that the graph contains a negative weight cycle.

In our example,

- A -> B (distance(B) = 2), no change
- A -> C (distance(C) = 3), no change
- B -> D (distance(D) = 2), no change
- C -> D (distance(D) = 3), no change
- B -> E (distance(E) = 2), no change
- D -> E (distance(E) = 2), no change

Since no distances can be further reduced, we confirm that the graph does not contain any negative weight cycles, and can now move to determine shortest paths.

**Step 4: Shortest paths**

We can now output the shortest paths from vertex A to every other vertex after the relaxation is finished and it is verified that there are no negative weight cycles.

**Vertex** |
**Distance from A** |
**Parent** |

A |
0 |
A |

B |
2 |
A -> B |

C |
3 |
A -> C |

D |
3 |
A -> B -> D |

E |
2 |
A -> B -> D -> E |

From the above table, we can finally output our shortest paths as:

- The shortest path from A to B is A -> B with a distance of 2.
- The shortest path from A to C is A -> C with a distance of 3.
- The shortest path from A to D is A -> B -> D with a distance of 3.
- The shortest path from A to E is A -> B -> D -> E with a distance of 2.

### Time Complexity

The Bellman-Ford algorithm has a time complexity of O(V * E). Let’s see how and when:

**Best Case Time Complexity:**

In the best case O(V * E), the Bellman-Ford will still run as it has to go through the relaxation step for all edges, even if no updates are required after the first few iterations. It does not stop prematurely like Dijkstra’s algorithm when all shortest paths have been found; therefore, the algorithm goes on V−1 iterations even if the solution has stabilised earlier.

For example, in case the input graph contains no negative weight edges and after one relaxation all distances are computed, Bellman-Ford would still go ahead with the remaining V−2 iterations.

**Worst Case Time Complexity: **

The worst case for the Bellman-Ford algorithm is when the graph has V large number of edges E relative to vertices (such as in a dense graph), the graph contains negative weight edges and a full set of V−1 relaxations must be done, the graph may have a negative weight cycle but still completes all relaxation steps before detecting that cycle. Therefore, the time complexity in the worst case will remain O(V * E).

### Space Complexity

The Bellman-Ford algorithm has an O(V + E) space complexity.

To store the shortest path estimates from the source vertex to each other vertex, the method keeps track of a distance array. O(V) space is required for this array, where V is the number of vertices.

Typically, the graph is shown as an edge list, with each edge connecting two vertices assigned a weight. O(E) space is needed in the edge list to hold all of the edges.

As a result, **O(V + E)** is the total space complexity, taking into consideration the edge list and distance array storage.