Bellman Ford

This page provides introduction to Bellman Ford Algorithm.

Overview

Bellman ford is single source shortest path algorithm. Below is a table showing the types of graphs where Bellman Ford algorithm works.

Graph Type	Does Bellman ford's Algorithm Works?
Directed with positive weight edge	Yes
Directed with negative weight edge	Yes(except when graph is negative weight cycle)
Undirected with positive weight edge	Yes
Undirected with negative weight edge	Yes(except when graph is negative weight cycle)

Here is example of graph with negative weight cycle.

Run Bellman Ford

Let's apply the Bellman Ford algorithm to the directed graph shown below to calculate the distance of each node from the source node $\text{A}$. The graph includes a negative weight edge, but no negative weight cycles.

We begin by iterating through each edge $\text{V} - 1$ times, where $\text{V}$ represents the number of vertices in the graph. Distance of node $\text{A}$ from itself is $0$.

Visiting edge $\text{AB}$ gives us the distance of node $\text{B}$ from $\text{A}$ as $50$, which is less than the existing value of infinity. Therefore, we update the distance for $\text{B}$ in the distance hashmap.

Visiting edge $\text{AC}$ gives us the distance of node $\text{C}$ from $\text{A}$ as $40$, which is less than the existing value of infinity. Therefore, we update the distance for $\text{C}$ in the distance hashmap.

Visiting edge $\text{AD}$ gives us the distance of node $\text{D}$ from $\text{A}$ as $5$, which is less than the existing value of infinity. Therefore, we update the distance for $\text{D}$ in the distance hashmap.

Visiting edge $\text{BC}$ gives us the distance of node $\text{C}$ from $\text{A}$ as $60$ (the distance of node $\text{B}$ from $\text{A}$ in the distance map plus the distance of edge $\text{BC}$). Since this is greater than the existing distance of node $\text{C}$ from $\text{A}$, we don't update anything in the distance hashmap.

Visiting edge $\text{BD}$ gives us the distance of node $\text{D}$ from $\text{A}$ as $70$ (the distance of node $\text{D}$ from node $\text{B}$ in the distance map plus the distance of edge $\text{BD}$). Since this is greater than the existing distance of node $\text{D}$ from $\text{A}$, we don't update anything in the distance hashmap.

Visiting edge $\text{DE}$ gives us the distance of node $\text{E}$ from $\text{A}$ as $9$ (the distance of node $\text{D}$ from $\text{A}$ plus the distance of edge $\text{DE}$). Since this is less than the existing value of infinity, we update the distance of node $\text{E}$ from $\text{A}$ in the distance hashmap.

Visiting edge $\text{EB}$ gives us the distance of node $\text{B}$ from $\text{A}$ as $-11$ (the distance of node $\text{E}$ from node $\text{A}$ plus the distance of edge $\text{EB}$).

This concludes the $1^{\text{st}}$ iteration of visiting all edges. Let's begin with the $2^{\text{nd}}$ iteration.

Visiting edge $\text{AB}$ gives us the distance of node $\text{B}$ from $\text{A}$ as $50$, which is greater than the existing distance of $-11$. Therefore, we don't update the distance in the hashmap.

Visiting edge $\text{AC}$ gives us the distance of node $\text{C}$ from $\text{A}$ as $40$, which is equal to the existing distance. Therefore, we don't update the distance in the hashmap.

Visiting edge $\text{AD}$ gives us the distance of node $\text{D}$ from $\text{A}$ as $5$, which is equal to the existing distance. Therefore, we don't update the distance in the hashmap.

Visiting edge $\text{BC}$ gives us the distance of node $\text{C}$ from $\text{A}$ as $-1$ (distance of $\text{B}$ from node $\text{A}$ + distance of edge $\text{BC}$), which is less than the existing distance. Therefore, we update the distance of node $\text{C}$ in the hashmap.

Visiting edge $\text{BD}$ gives us the distance of node $\text{D}$ from $\text{A}$ as $8$ (distance of $\text{B}$ from node $\text{A}$ + distance of edge $\text{BD}$), which is greater than the existing distance. Therefore, we don't update the distance in the hashmap.

Visiting edge $\text{DE}$ gives us the distance of node $\text{E}$ from $\text{A}$ as $9$ (distance of $\text{D}$ from node $\text{A}$ + distance of edge $\text{DE}$), which is equal to the existing distance. Therefore, we don't update the distance in the hashmap.

Visiting edge $\text{EB}$ gives us the distance of node $\text{B}$ from $\text{A}$ as $-11$ (distance of $\text{E}$ from node $\text{A}$ + distance of edge $\text{EB}$), which is equal to the existing distance. Therefore, we don't update the distance in the hashmap.

This concludes the $2^{\text{nd}}$ iteration of visiting all edges. Continuing the $3^{\text{rd}}$ and $4^{\text{th}}$ iterations yields similar results for the distance hashmap, as no further updates are made. At this point, the shortest distances from the source node $\text{A}$ to all other nodes have been finalized.

Why V - 1 Iterations

Let's say we have the following graph, and we are finding the shortest path from node $\text{A}$ using the Bellman Ford algorithm.

Now, if we apply the Bellman-Ford algorithm to the graph above, the first edge we iterate over will be $\text{BC}$. Since we don't yet know how to reach node $\text{B}$, we can't update the distance hashmap.

Now, we iterate over the edge $\text{AB}$. Since the distance of $\text{A}$ from itself is already known, we can update the distance of node $\text{B}$ from node $\text{A}$ to $10$.

This concludes the $1^{\text{st}}$ iteration, but we still haven't determined the distance of node $\text{C}$ from node $\text{A}$. This happened because when we first iterated over edge $\text{BC}$, we didn't know the distance of node $\text{B}$ from node $\text{A}$.

This demonstrates that the algorithm's effectiveness also depends on the order in which we iterate over the edges. Iterating over the edges $\text{V} - 1$ times ensures that we have updated the shortest distances for all nodes, even if some connections were discovered in later iterations.

Therefore, in the Bellman Ford algorithm, we iterate over the edges $\text{V} - 1$ times to ensure that all shortest paths are correctly updated.

Java

class Edge {
  char src;
  char dest;
  int distance;

  Edge(char src, char dest, int distance) {
    this.src = src;
    this.dest = dest;
    this.distance = distance;
  }
}

public HashMap<Character, Integer> bellmanFord(int vertices, Edge[] graph) {
  HashMap<Character, Integer> dist = new HashMap<>();
  for(int i = 0; i < vertices; i++) {
    char ch = 'A' + i;
    dist.put(ch, Integer.MAX_VALUE);
  }
  // source node
  dist.put('A', 0);

  for(int i = 0; i < vertices - 1; i++) {
    for(Edge e: graph) {
      if(dist.get(e.src) != Integer.MAX_VALUE && dist.get(e.src) + e.distance < dist.get(e.dest)) {
        dist.put(e.dest, dist.get(e.src) + e.distance);
      }
    }
  }

  // run the algorithm one more time to check if graph has negative weight cycle
  for(Edge e: graph) {
    // distance reduces futher meaning graph as negative weight cycle
    if(dist.get(e.src) != Integer.MAX_VALUE && dist.get(e.src) + e.distance < dist.get(e.dest)) {
      throw new Excepttion("Graph contains negative weight cycle");
    }
  }
  return dist;
}

Complexity

Let's say there are $\text{V}$ vertices and $\text{E}$ edges in a graph.

Time Complexity

Bellman ford algorithm runs for $\text{V} - 1$ times over all the edges, so time complexity is:

$$\text{O(V E)}$$

Space Complexity

The algorithm uses space to store the distances of all vertices in a hashmap, therefore the total space complexity will be as below:

$$\text{O(V)}$$

info

Bellman Ford is useful for graphs with negative weights, but Dijkstra’s algorithm is typically preferred when all edge weights are non negative.