我正在尝试使用map reduce实现dijkstra的最短路径算法。
我有两个问题：
-
如果未选择路径的距离变小，该算法是否会回溯以重新评估距离。例如->1->2->5和2->3->2将这些值视为权重，并且到目的地路径1的可能的2条路径将被选择为1<2，但路径2的权重总和较小，即2->3->2，所以想知道dijkstra的算法是否考虑了回溯。
-
请给我一个简单的想法，地图和减少功能将如何在这种情况下。我正在考虑在map函数中发射，在reduce函数中，在reduct函数中我迭代相关的权重，以找到加权最小的邻居。。但在那之后它是如何运作的。请告诉我它是如何在集群中从头开始发生的，以及内部发生了什么。
Dijkstra不执行回溯来重新评估距离。
http://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif
这个gif应该可以帮助你理解Dijkstra的算法是如何重新评估距离的。它通过在节点n内存储"到节点n的最短路径"来避免回溯的任务。
在遍历过程中，如果算法再次遍历节点n，它将简单地比较到达节点n的当前"距离"，并将其与存储在节点n中的数据进行比较
然而，Dijkstra在处理负边缘时有一个局限性，因为在某些情况下，你可能会陷入负循环，所以这是你应该警惕的。