Bellman–Ford algorithm

Bellman-Ford can handle graphs with negative edge weights, unlike Dijkstra's algorithm. It has a time complexity of O(V * E), where V is the number of vertices and E is the number of edges.

Hint

Initialization:

• Initialize dist array with infinity for all nodes except the source, which has a distance of 0.
• Initialize parent array to store the predecessor of each node in the shortest path.

Relaxation:

• Iterate V - 1 times (where V is the number of vertices).
• In each iteration, examine each edge in the graph.
• If the distance to the current node plus the weight of the edge is less than the current distance to the neighbor, update the distance to the neighbor and its predecessor.

Negative Cycle Detection:

• After V - 1 iterations, perform one more iteration.
• If any distance can be further reduced, it indicates the presence of a negative-weight cycle in the graph.

Result:

• If no negative-weight cycles are found, the dist array contains the shortest distances from the source node to all other nodes.
• The parent array can be used to reconstruct the shortest paths.

• Python
• Javascript
•  Run

def bellmanFord(graph, src):
  dist = {}
  prev = {}
  V = len(graph)

  for node in graph:
    dist[node] = float('inf')
    prev[node] = None
  
  dist[src] = 0
  
  for i in range(0, V - 1):
    for v in graph:
      for n in graph[v]:
        weight = graph[v][n]
        if dist[v] != float('inf') and dist[v] + weight < dist[n]:
          dist[n] = dist[v] + weight
          prev[n] = v

  for v in graph:
    for n in graph[v]:
      weight = graph[v][n]
      if dist[v] != float('inf') and dist[v] + weight < dist[n]:
        return None

  return { dist, prev }

graph = {
  'A': {'B': -1, 'C': 4},
  'B': {'C': 3, 'D': 2, 'E': 2},
  'C': {},
  'D': {'B': 1, 'E': -3},
  'E': {'D': -3}
}
source = 'A'
result = bellmanFord(graph, source)

print(result.dist if result else 'Graph contains negative weight cycle.')

function bellmanFord(graph, src) {
  const dist = {};
  const prev = {};
  const V = Object.keys(graph).length;

  for (const node in graph) {
    dist[node] = Infinity;
    prev[node] = null;
  }
  dist[src] = 0;
  
  for (let i = 0; i < V - 1; i++) {
    for (const v in graph) {
      for (const n in graph[v]) {
        const weight = graph[v][n];
        if (dist[v] !== Infinity && dist[v] + weight < dist[n]) {
          dist[n] = dist[v] + weight;
          prev[n] = v;
        }
      }
    }
  }

  for (const v in graph) {
    for (const n in graph[v]) {
      const weight = graph[v][n];
      if (dist[v] !== Infinity && dist[v] + weight < dist[n]) {
        return null;
      }
    }
  }

  return { dist, prev };
}

const graph = {
  'A': {'B': -1, 'C': 4},
  'B': {'C': 3, 'D': 2, 'E': 2},
  'C': {},
  'D': {'B': 1, 'E': -3},
  'E': {'D': -3}
};
const source = 'A';
const result = bellmanFord(graph, source);

console.log(result ? result.dist : 'Graph contains negative weight cycle.');