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.
Initialization:
Relaxation:
Negative Cycle Detection:
Result:
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.');