Algorithm Bellman-Ford is in its basic structure very similar to Dijkstra's algorithm<http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm>, but instead of greedily selecting the minimum-weight node not yet processed to relax, it simply relaxes *all* the edges, and does this |*V*| - 1 times, where |*V*| is the number of vertices in the graph. The repetitions allow minimum distances to accurately propagate throughout the graph, since, in the absence of negative cycles, the shortest path can only visit each node at most once. Unlike the greedy approach, which depends on certain structural assumptions derived from positive weights, this straightforward approach extends to the general case.
Bellman-Ford runs in *O <http://en.wikipedia.org/wiki/Big_O_notation>*(|*V* |ยท|*E*|) time, where |*V*| and |*E*| are the number of vertices and edges respectively. *procedure* BellmanFord(*list* vertices, *list* edges, *vertex* source) *// This implementation takes in a graph, represented as lists of vertices* *// and edges, and modifies the vertices so that their *distance* and* *//* predecessor *attributes store the shortest paths.* *// Step 1: Initialize graph* *for each* vertex v in vertices: *if* v *is* source *then* v.distance := 0 *else* v.distance := *infinity* v.predecessor := *null* *// Step 2: relax edges repeatedly* *for* i *from* 1 *to* size(vertices)-1: *for each* edge uv in edges: *// uv is the edge from u to v* u := uv.source v := uv.destination *if* u.distance + uv.weight < v.distance: v.distance := u.distance + uv.weight v.predecessor := u *// Step 3: check for negative-weight cycles* *for each* edge uv in edges: u := uv.source v := uv.destination *if* u.distance + uv.weight < v.distance: *error* "Graph contains a negative-weight cycle" Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay On Mon, Dec 14, 2009 at 11:40 AM, vicky <[email protected]> wrote: > What is the difference between Dijkstra's algorithm and Bellman-Ford's > algorithm? > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
