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:

Relaxation:

Negative Cycle Detection:

Result:

# Python implementation
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.')
// Javascript implementation
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.');