(1188 Views)

There are plenty of algorithms to learn for getting better at programming. One such algorithm is the Bellman Ford algorithm that is used in the graph search. Let us know about it in detail.

It is used for finding the shortest path between a source vertex to all the other vertices in a weighted digraph. However, the Bellman Ford Algorithm can also be used for the unweighted graph. It is basically known as the path-finding algorithm and sometimes as Bellman–Ford–Moore algorithm.

There is a similar algorithm known as the Dijikstras algorithm but Bellman Ford Algorithm is better in terms of versatility. The only issue is that it is a little slow but it can handle the graphs having negative edge weights. Negative edge weights have various uses in graphs.

The first proposal of this algorithm was given by Alfonso Shimbel in 1955. It is named after Richard Bellman and Lester Ford Jr in 1958 and 1959. It was published again by Edward F. Moore in 1957.

This algorithm uses graph data structure as it solves the weighted graph search problem. It has many applications like in calculating the shortest distance between two locations in Google Maps, distance vector routing protocol, and so on.

Let A is the source vertex. In the first step, it is initialized that the distance is infinite excluding the distance to the source. As the total numbers of edges are 5 so they will be processed for 4 times.

Assuming that all the edges are processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D), we will get the given distances. The first row is showing initial distance, the second row is showing the distance when edges (B, E), (D, B), (B, D) and (A, B) are dealt with, and the third row is showing the distances after processing (A, C). The last row is showing distance after processing (D, C), (B, C) and (E, D).

From the first iteration, you will get the shortest path of at most 1 edge long. When the edges will be processed for the second time then you will get the give distances. Similarly, the second iteration provides the shortest path at most 2 edges long. All edges are processed twice and distances are reduced after the second iteration gets over. Assuming that all the edges are processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D), we will get the given distances. The first row is showing initial distance, second row is showing the distance when edges (B, E), (D, B), (B, D) and (A, B) are dealt with, and the third row is showing the distances after processing (A, C). The last row is showing distance after processing (D, C), (B, C) and (E, D).

1 UpvotesUpvote |
3 DownvotesDownvote |

- Create an Augmented Reality (AR) Android App using Unity and Artoolkit [3909 Views]
- Funny Programming Memes [5342 Views]
- [Solved] Can MIN() and MAX() functions be used with Date columns in Oracle SQL [792 Views]
- Writable Streams in Javascript [1114 Views]
- Add a column with a default value to a table in Oracle SQL [809 Views]

- How To Win Ludo King Game Every Time [22612 Views]
- Algorithm to find whether number is Armstrong Number or Not [21827 Views]
- Jio Phone hang on LOGO problem Solution - Hard Reset Jio Phone [14858 Views]
- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [14330 Views]
- FlowChart and Algorithm to find Whether a Number is Even or Odd [10901 Views]