我正在尝试使用map reduce实现dijkstra的最短路径算法。
我有两个问题：
如果未选定路径的距离变小，则此算法是否会回溯以重新评估距离。例如->1->2->5和2->3->2将这些值视为权重，目标路径1的可能2条路径将被选择为1<2，但路径2的总权重总和小于2->3->2，因此想知道dijkstra的算法是否考虑回溯。
请给我一个简单的想法，如何Map和减少功能将在这种情况下。我想在map函数中发射，在reduce函数中，在reduce函数中，我迭代相关的权重，以找到加权最小的邻居..但在那之后它是如何工作的。请给我一个很好的主意，它是如何从零开始在集群中发生的，以及内部发生了什么。
1条答案
按热度按时间pgpifvop1#
dijkstra不执行回溯来重新评估距离。
http://upload.wikimedia.org/wikipedia/commons/5/57/dijkstra_animation.gif
这个gif可以帮助你理解dijkstra的算法是如何重新计算距离的。它通过在节点n中存储“到节点n的最短路径”来避免回溯任务。
在遍历过程中，如果算法再次遇到节点n，它只需比较它遍历到节点n的当前“距离”，并将其与存储在节点n中的数据进行比较。如果较大，则忽略它；如果较小，则保留替换节点n中的数据。
然而，dijkstra的方法在处理负边缘时有一个局限性，因为在某些情况下，你可能会以负循环结束，所以这是你应该警惕的。