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

我有两个问题:

  • 如果未选择的路径的距离变短,此算法是否回溯以重新评估距离。例如-> 1-> 2-> 5和2-> 3-> 2认为这些值是权重,到目标路径1的可能2条路径将被选择为1 3-> 2,所以想知道dijkstra的算法是否处理了回溯。
  • 请简要介绍一下map和reduce函数在这种情况下的情况。我正在考虑在map函数中以及在reduce函数中以及在reduce函数中进行发射,我对关联的权重进行迭代以找到加权最小的邻居..但是在那之后它是如何工作的。请给我一个好主意,说明它是如何从头开始在群集中发生的以及内部发生的情况。
  • 最佳答案

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

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

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

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

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

    关于hadoop - dijkstra的最短路径算法回溯了吗?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/20452445/

    10-12 22:51