Bellman-Ford Algorithm
An algorithm that computes shortest paths from a single source vertex to all other vertices in a weighted digraph, even with negative edge weights.
Visualization
Details
Analogy
Imagine a currency exchange market with various conversion rates. Some 'rates' (edges) might be beneficial (negative weight) due to arbitrage opportunities. You want to find the 'cheapest' way to convert your home currency to all others. Bellman-Ford is like iterating through all possible trades (edges) many times. Each time, you see if a new trade can give you a better deal for any currency. After enough iterations, you'll have the best rates. If prices keep getting better indefinitely, it means there's a profitable loop (a negative cycle).
Purpose
To find the shortest paths from a source to all other nodes in a graph that may contain negative edge weights. It can also detect negative weight cycles.
Use Cases
Used in routing protocols where edge weights can represent various metrics, and for detecting arbitrage opportunities in finance. It's slower than Dijkstra's but more versatile due to its ability to handle negative weights.
Algorithm Steps
initialize distances to infinity, dist[start] = 0
for i = 1 to V-1:
for each edge (u, v) with weight w:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for each edge (u, v) with weight w:
if dist[u] + w < dist[v]:
return 'Negative cycle detected'
return dist
Explanation
What's Happening?
Initialize distances: S=0, others=∞.
Code Implementation
def bellman_ford(graph, start_node):
distances = {node: float('inf') for node in graph}
distances[start_node] = 0
num_vertices = len(graph)
for _ in range(num_vertices - 1):
for u, edges in graph.items():
for v, weight in edges.items():
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
# Check for negative weight cycles
for u, edges in graph.items():
for v, weight in edges.items():
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
return "Graph contains a negative weight cycle"
return distances