我正在尝试使用map reduce实现dijkstra的最短路径算法。
我有两个问题:
最佳答案
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/