java - 对 Dijkstra 算法特定实现的小修改

Question

在过去的几周里，作为个人项目的一部分(主要是为了测试性能)，我一直在研究 Dijkstra 算法的各种实现。我最近遇到了this implementation我测试过的算法和所有内容。但是，我目前正在尝试修改该实现，因此它需要一个额外的参数来表示目标节点，这意味着我希望算法从指定的源到指定的目标只运行一次，而不是图中的所有其他节点.

我尝试添加第三个 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;
}

Answer 1

Dijkstra 算法的工作原理是寻找从源节点到图中每个其他节点的最短路径。当然，一旦它找到到目标节点的最短路径，您就可以提前终止它，但这不一定会带来很大的加速。

不过，如果您真的想加快寻找最短路径的速度，“中间相遇”技巧可能会很有用。您同时运行来自源的最短路径和来自汇的最短路径(将每条边视为其反向)；一旦两次搜索都到达同一个节点，您就可以重建一条从源到目标的最短路径。

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

我还应该指出，此代码的另一个非常非常简单的优化是停止将所有内容包装在对象中。你在空间和速度上付出了很多代价，将 double 包装在 Double 类中，无论你的 Node 在类中是什么