What is Bellman Ford Algorithm ?

( Find shortest path )

History of Bellman-Ford  Algorithm 

The bellman ford algorithm was first proposed by Alfonso Shimbel in 1955

Named after Richard Bellman and Lester Ford Jr who published it in 1956 and 1958

Definition Bellman-Ford  Algorithm

The bellman-ford algorithm is an algorithm that computes shortest path from a single source vertex to all of the other vertices in a weighted graph.

It is an alternative of Dijkstra’s algorithm because it is more versatile, as it is capable of handling graph in which some of the edge weights are negative numbers. 

 Pseudo Code Bellman-Ford  Algorithm

·                           BELLMAN-FORD (G,w,s)

·                           INITIALIZE-SINGLE-SOURCE(G, s)

·                           for i = 1 to |G.V| -1

·                           for each edge (u,v) Є G.E

·                           RELAX (u,v,w)

·                           for each edge (u,v) Є G.E

·                           if v.d > u.d + w (u,v)

·                          return FALSE

·                          return TRUE

Time complexity Bellman-Ford  Algorithm

  Bellman -Ford algorithm runs  in O(|G.V| |E|)

Application Bellman-Ford  Algorithm

In a telephone network the lines have bandwidth (BW), we want to route the phone call via the highest(BW) and consider the transmission lines with highest BW as shortest path .

·                            Consider telephone network as a GRAPH

·                            Switching station in the network are our VERTICES

·                            Transmission lines in the network are EDGES

·                            Bandwidth in network are WEIGHTS