Bellman-Ford Algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.. It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by Alfonso Shimbel in 1955, but is instead named after Richard Bellman and Lester Ford, Jr., who published it in 1958 and 1956, respectively. Bellman-Ford Equation dx(y) = min {c(x,v) + dv(y) } where min is taken over all neighbors v of x Steps: 1) This step initializes distances from source to all vertices as infinite and distance to source itself as 0.
Create an array dist of size |V| with all values as infinite except distsrc where src is source vertex. 2) This step calculates shortest distances. Do following |V|-1 times where |V| is the number of vertices in given graph. Do following for each edge u-v If distv ; distu + weight of edge uv, then update distv distv = distu + weight of edge uv