hadoop - dijkstra的最短路径算法回溯了吗？

Question

我正在尝试使用map reduce实现dijkstra的最短路径算法。

我有两个问题:

如果未选择的路径的距离变短，此算法是否回溯以重新评估距离。例如-> 1-> 2-> 5和2-> 3-> 2认为这些值是权重，到目标路径1的可能2条路径将被选择为1 <2，但是路径的权重总和较小2是2-> 3-> 2，所以想知道dijkstra的算法是否处理了回溯。

请简要介绍一下map和reduce函数在这种情况下的情况。我正在考虑在map函数中以及在reduce函数中以及在reduce函数中进行发射，我对关联的权重进行迭代以找到加权最小的邻居..但是在那之后它是如何工作的。请给我一个好主意，说明它是如何从头开始在群集中发生的以及内部发生的情况。

Answer 1

Dijkstra不会执行回溯来重新评估距离。

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

gif应该可以帮助您了解Dijkstra的算法如何重新评估距离。通过将“到节点n的最短路径”存储在节点n内，可以避免回溯的任务。

在遍历期间，如果算法再次遇到节点n，它将简单地比较遍历以到达节点n的当前“距离”并将其与存储在节点n中的数据进行比较。如果该值较大，它将忽略它；如果较小，它将保持替换节点n中的数据。

但是，Dijkstra在处理负边缘时有一个局限性，因为在某些情况下您可能会遇到负周期，因此您应该提防这一点。