Dijkstra算法特殊实现的小修改

在过去的几周里，我一直在玩Dijkstra算法的各种实现作为个人项目的一部分（主要是为了测试性能）。我最近碰到了算法的this implementation，我已经测试了一切。但是，我正在尝试修改该实现，因此它需要一个额外的参数来表示目标节点，这意味着我希望算法仅从指定的源运行一次到指定的目标，而不是图中的所有其他节点。Dijkstra算法特殊实现的小修改

我尝试添加第三targetNode参数，但在执行中发现的dest变量是Entry<T>型的，我的参数是Node型（自定义类我写的），所以我最终得到了一个不兼容的类型的错误消息。

是否有可能以某种方式进行此修改？我用另一个实现很容易做到了，但我似乎无法解决这个问题，主要是由于不同的类型Node和Entry<T>。这不是什么大不了的事情，但我想这样做。

谢谢！

编辑：这就是我所做的：

public static <Node> Map<Node, Double> dijkstraFibonacciHeap(DirectedGraph<Node> graph, Node source, Node target) { 
    FibonacciHeap<Node> priorityQueue = new FibonacciHeap<>(); 
    Map<Node, FibonacciHeap.Entry<Node>> entries = new HashMap<>(); 
    Map<Node, Double> result = new HashMap<>(); 

    for (Node node : graph) { 
     entries.put(node, priorityQueue.enqueue(node, Double.POSITIVE_INFINITY)); 
    } 


    priorityQueue.decreaseKey(entries.get(source), 0.0); 

    while (!priorityQueue.isEmpty()) { 

     FibonacciHeap.Entry<Node> curr = priorityQueue.dequeueMin(); 

     result.put(curr.getValue(), curr.getPriority()); 

     for (Map.Entry<Node, Double> arc : graph.edgesFrom(curr.getValue()).entrySet()) { 

      if (result.containsKey(arc.getKey())) { 
       continue; 
      } 

      double pathCost = curr.getPriority() + arc.getValue(); 

      // Error occurrs here. 
      target = entries.get(arc.getKey()); 
      if (pathCost < target.getPriority()) { 
       priorityQueue.decreaseKey(target, pathCost); 
      } 
     } 
    } 
    return result; 
}

来源

2013-04-10 Fiery Phoenix

请发布您正在尝试的实际代码片段。 – 2013-04-10 18:25:02

完成。谢谢你提醒我。 – 2013-04-10 18:31:00

Dijkstra算法的工作原理是寻找到图中的所有其他节点从源节点的最短路径。当然，一旦它找到到目标节点的最短路径，就可以尽早终止它，但这并不一定会导致很大的加速。

尽管如此，如果你真的想加快寻找最短路径，那么“中间相遇”技巧会很有用。你从源头运行最短路径，同时使用最短路径（将每条边作为反向）;一旦两次搜索都到达同一节点，就可以重建最短的源到目标路径。

如果您对图表的外观有很好的猜测，A *是另一种方法。

我还应该指出，对这段代码的另一个真正简单的优化是停止将所有对象都包装起来。你在太空和速度方面付出了很多，因为double s在Double课程中，以及你的Node也在课堂上。

来源

2013-04-10 18:33:40 tmyklebu

嗯，我想我会坚持原来的想法，并使用正常的算法。说实话，我只是试图进行一次特定的性能测试，但由于只从源头向目标运行算法一次不会导致很大的加速，所以这并不重要。感谢您的提醒。 – 2013-04-10 18:50:13

Dijkstra算法特殊实现的小修改

回答

相关问题