Bellman-Ford Algorithm, which can apply on weighted Graph Data Structure, to find the shortest path between a source vertex to all other vertices. The algorithms can be only be applied on the weighted Graph, with negative weight edges. Though we have Dijkstra’s Algorithm to find the shortest path between vertices, it can not find the shortest path if the graph contains negative weight edges, so for that, we use the Bellman-Ford Algorithm. There is a shortcoming in the Bellmen-Ford algorithm too if a graph contains a cycle in which total weight in negative then even the Bellmen-Ford Algorithm would not be able to show the shortest path of that Graph. Its drawback, not to work with a negative cycle can come handy to find whether the Graph contains a negative cycle or not.
What is Bellmen-Ford Algorithm?
We can Apply Bellmen-Ford Algorithm on a weighted graph G, which have finite number of vertices, V, and weighted Edges E. We also need to specify the source vertex, from which we want to calculate the distance of all the other vertices, in Bellmen-Ford algorithm we do not need to specify the final vertex, the algorithm itself find all the shortest distance from source vertices to all other vertices present in the Graph. The Bellmen-Ford Algorithms works on the principle of relaxation to find the shortest path of all vertices from the source vertex. In programming, we can relate relaxation to the number of times we perform a complete iteration over a graph. The relaxation of a graph depends on the vertices present in the graph if there are n vertices in the graph the relaxation would be n-1.
Infinite solution by the Bellmen-Ford Algorithm
While we use the Bellmen-Ford Algorithm we need to take care of two issues, which are:
- The Graph Should not contain a negative weight cycle
- Do not choose a bad ordering for relaxation.
If we ignore the above two issues, the search for the shortest path by the algorithm will go on forever.
Bellmen-Ford Algorithm Pseudo-Code
for v in V: v.distance = infinity v.p = None source.distance = 0 for i from 1 to |V| - 1: for (u, v) in E: relax(u, v) The first for loop sets the distance to each vertex in the graph to infinity. This is later changed for the source vertex to equal zero. Also, in that first for loop, the p-value for each vertex is set to nothing. This value is a pointer to a predecessor vertex so that we can create a path later. The next for loop simply goes through each edge (u, v) in E and relaxes it. This process is done |V| - 1 time. Relaxation Equation
Algorithm
- The First step to initialize the distance, set all the vertices at distance infinity from the source vertex and set the source vertex at distance 0 from itself. In programming you can perform this action by creating an array, arr[v] where v is the number of vertices in the graph, set all the values of array infinity except the arr[0] which is the source vertex and set it 0.
- The second step to iterate over the Graph |v-1| times, and calculate the shortest distance. Perform the statement:
If arr[v] > arr[u] + weight of edge uv: Update arr[v] by arr[v] = arr[v]+weight of edge uv
Bellmen-Ford Implementation in Python
def BellmanFord(graph, V, E, src):
arr = [float('inf')] * V
arr[src] = 0
for i in range(V - 1):
for j in range(E):
if arr[graph[j][0]] + graph[j][2] < arr[graph[j][1]]:
arr[graph[j][1]] = arr[graph[j][0]] + graph[j][2]
for i in range(E):
x = graph[i][0]
y = graph[i][1]
weight = graph[i][2]
if arr[x] != maxsize and arr[x] + weight < arr[y]:
print("Graph with negative weight cycle")
print("All Vertices Distance")
for i in range(V):
print("%d\t\t%d" % (i, arr[i]))
People are also reading:
Leave a Comment on this Post