Bellman-Ford Algorithm

By starting from the source , you have to reach all other vertices via the shortest path What you do to achieve the solution . In this case as no negative weight is there so you will choose Dijkstra’s algorithm. BUT IF NEGATIVE WEIGHT WERE GIVEN WHAT YOU WILL DO ?

A new algorithm is needed in this scenario

Bellman-Ford Algorithm computes shortest path from one source vertex to all or any of the opposite vertices during a weighted digraph.It solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted , directed graph G = (V,E) with source s and weight function w : E -> R.

Returns TRUE ( if there is no-negative-weight-cycle)

Returns FALSE(if there is a negative cycle reachable from source vertex)

• It can be implemented easily in a distributed manner.
• Time complexity is O(VE).
• It is slower than Dijkstra’s for an equivalent problem but more versatile because it is capable of handling graphs in which some of the edges weight are negative numbers.
• It works on the principle of relaxation

In fig. (a)Bellman Ford algorithm can find the shortest path from source as no negative-weight cycle exist . (b) No solution exists due to negative-weight cycle

How does this work ?

By using a bottom-up approach, this algorithm determines the shortest paths.Initially, it calculates the shortest distances with at-most one intersection in the path.After that, it calculates the shortest paths with at-most two edges, etc.At the end of the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated.In a simple path there can be no more than V — 1 edges, therefore the outer loop runs v — 1.Having assumed that there is no negative cycle of weight, if we have determined the shortest paths with i edges at most, we are able to iterate At-most (i+1) edges can be found in the shortest path from all edges.

In fig. (a) It is in the initial configuration phase.From source vertex a, All values appear within the vertices, and shaded edges indicate predecessor values. In this case, each pass relaxes the edges in the order (b,d),(b,c),(b,e),(d,b),(c,d),(c,e),(e,d),(e,a),(a,b),(a,c)Then vertices b and c were reached and their distances from vertex a were updated.

Figure (d) shows that the distance between the paths a -> b -> d is 1 + 4 = 6, while the distance between the paths a -> c -> d is 4 + (-2) = 2. Therefore, path a -> c -> d is preferred which is shown in red.

The Bellman-Ford algorithm returns TRUE in this case