Welcome to another exciting lesson on Data Structures and Algorithms at CodeYourCraft! Today, we're diving deep into the Bellman-Ford Algorithm, a powerful tool for finding the shortest path in a graph with negative edge weights. Let's get started! š
The Bellman-Ford Algorithm is an algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted graph. It can handle graphs with negative edge weights and also detect negative cycles, which some other algorithms can't. š”
The Dijkstra's Algorithm, which we've covered earlier, doesn't work with negative edge weights. The Bellman-Ford Algorithm is a perfect alternative in such cases. Let's understand it step by step.
The Bellman-Ford Algorithm has two phases: Relaxation and Check for Negative Cycle.
Initialize dist[s] (the source vertex) as 0 and dist[v] as INF (Infinity) for all other vertices v.
For V-1 iterations:
(u, v) with weight w, if dist[u] + w < dist[v], then update dist[v] = dist[u] + w.Run one final relaxation pass. If any vertex's distance is updated, then there is a negative cycle.
If no vertex's distance is updated in the final relaxation pass, then there are no negative cycles. If a vertex's distance is updated, then there is a negative cycle.
Here's a simple Python implementation of the Bellman-Ford Algorithm:
import sys
INF = float('inf')
def bellman_ford(graph, src):
n = len(graph)
dist = [INF] * n
dist[src] = 0
for i in range(n - 1):
for u in range(n):
for v in range(n):
if graph[u][v] != INF and dist[u] != INF and dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
for u in range(n):
for v in range(n):
if graph[u][v] != INF and dist[u] != INF and dist[u] + graph[u][v] < dist[v]:
print("Graph contains a negative cycle.")
sys.exit()
return distThe Bellman-Ford Algorithm is useful in various real-world scenarios such as airline ticket booking, delivery services, network routing, and more. š”
That's all for today! We've covered the Bellman-Ford Algorithm with negative weights and learned its importance in handling graphs with negative edge weights. Stay tuned for more exciting lessons on Data Structures and Algorithms at CodeYourCraft! š