dijkstra's shortest path algorithm backtracks?

Question

I am trying to implement dijkstra's shortest path algorithm using map reduce.

I have two questions:

1. Does this algorithms backtracks to re-evaluate the distances in case the distance turns out to be less for not selected path. For example-> 1->2->5 and 2->3->2 consider these values to be weights and possible 2 paths to a destination path 1 would be selected as 1<2 but overall sum of weights is less for path 2 that is 2->3->2 so want to know if dijkstra's algorithm takes care of backtracking.

2. Please give me a brief idea of how map and reduce function will be in this case. I am thinking of emitting in map function as and in reduce function and in reduce function I iterate over associated weights to find the least weighted neighbour ..but after that how it function. Please give me a good idea of how it happens from scratch in a cluster and what happens internally.

Answer 1

Dijkstra's does not perform backtracking to re-evaluate the distances.

http://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif

that gif should help you understand how Dijkstra's algorithm re-evaluate distances. It avoids the task of backtracking by storing the "shortest path to node n" inside node n.

During traversal if the algorithm comes across node n again, it will simply compare the current "distance" it traversed to get to node n and compare it to the data stored in node n. If it is greater it ignores it and if it is lesser it keeps replaces the data in node n.

Dijkstra's however has a limitation when dealing with negative edges since you could end up with a negative cycle in some circumstances, so that is something you should be wary of.