1

Over the past few weeks I've been playing with a variety of implementations of Dijkstra's algorithm as part of a personal project (mainly to test performance). I have recently come across this implementation of the algorithm, which I have tested and everything. However, I'm currently trying to modify that implementation so it takes an additional argument to represent the destination node, which means I want the algorithm to run only once from a specified source to a specified destination rather than to all other nodes in the graph.

I tried adding a third targetNode parameter but the dest variable found in the implementation is of type Entry<T> and my parameter was of type Node (a custom class I wrote), so I eventually got an incompatible types error message.

Is it possible to somehow make this modification? I did it easily with another implementation but I can't seem to figure it out for this one mainly due to the different types Node and Entry<T>. It's not really a big deal but I would like to do it.

Thanks!

EDIT: Here's what I did: 

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;
}
4

1 回答 1

0

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

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

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

我还应该指出，对这段代码的另一个非常非常简单的优化是停止将所有内容包装在对象中。您为将 s 包装double在类中Double以及您Node的 s 在类中的任何内容付出了很多，无论是在空间上还是在速度上。

于 2013-04-10T18:33:40.593 回答