java - 将现有的Fibonacci堆Java实现与Dijkstra的最短路径Java实现一起使用

利用java编程语言，在一个边成本为正的图上实现最有效的最短路径算法。据我所知，这将是Dijkstra的算法，使用Fibonacci堆作为优先级队列我借用了Keith Schwarz在链接中描述的Fibonacci堆实现http://keithschwarz.com/interesting/code/?dir=fibonacci-heap
在我的代码中，我还修改了这个问题中提出的dijkstra算法实现，
Java: Using a Fibonacci Heap for Implementing Dijkstra's Algorithm
这是根据我的实现更新的dijkstra，

public static void SPFibonacciHeap() {
    {

        FibonacciHeap<Node> myHeap = new FibonacciHeap<Node>();

        //adding all nodes to the PQ (heap)
        for(int i=0; i<nodeList.size(); i++)
                    myHeap.enqueue(nodeList.get(i), nodeList.get(i).d);

        while (!myHeap.isEmpty()) {

            //deque the minimum (first iteration will be the source)
            Entry<Node> u = myHeap.dequeueMin();


            // Visit each edge connected from u
            for (AdjacentNode a : u.getValue().adjacents) {

                //getting the adjacent node
                Node v = a.node;
                Entry<Node> vEntry = new Entry<Node>(v,v.d);//WRONG

                //getting the edge weight
                double weight = a.cost;

                double distanceThroughU = u.getValue().d + weight;
                if (distanceThroughU < v.d) {
                    v.d = distanceThroughU;
                    myHeap.decreaseKey(vEntry, v.d); //SHOWS ERROR
                    v.parent = u.getValue();
                }
            }
        }
    }
}

这是我的节点和邻接节点类，

class Node{

    Double [] label;
    double d; //node cost
    ArrayList<AdjacentNode> adjacents;
    Node parent;

    public Node(Double[] label, double d,ArrayList<AdjacentNode> adjacents)
    {
        this.label= label;
        this.d=d;
        this.adjacents=adjacents;
        parent=null;

    }




}


class AdjacentNode
{
    Node node;
    double cost;

    public AdjacentNode(Node node, double cost)
    {
        this.node= node;
        this.cost=cost;
    }
}

一切都很顺利，直到我想减少下一行的键，

myHeap.decreaseKey(vEntry, v.d);

我面临的问题是vEntry应该是堆中已经存在的节点。但是，我无法从堆中检索此节点，因为我可以考虑检索相邻节点v的唯一方法是使用节点u中的邻接列表但是，在下面的行中，我错误地将它表示为一个新的入口节点，

Entry<Node> vEntry = new Entry<Node>(v,v.d);

然而，这将创建一个新的条目来保存我正在寻找的节点，而不是在我寻找的节点堆中存在的条目。这将导致预期的空指针异常。
我想不出解决这个问题的办法对于这个堆实现来说，获取与给定节点项相邻的节点项似乎是不可能的吗？有人能帮忙吗？谢谢您。

最佳答案

所以这是我的密码。：-）我想我也许能帮上忙。
如果您注意到了，enqueue方法返回一个Entry<T>表示Fibonacci堆中与您刚刚排队的对象相对应的内部条目其目的是，当您将某物排队到Fibonacci堆中时，您将把返回的Entry<T>保存到某个地方，以便以后使用它实际上我的网站上也有an implementation of Dijkstra's algorithm的内容我做这项工作的方法是将第二个Map从节点存储到Entry对象，以便在需要调用decreaseKey时，可以查找与给定节点对应的Entry，然后将其传递到decreaseKey。
作为一个总结，虽然dijkstra的fibonacci堆算法在理论上比使用普通二进制堆的算法快，但在实践中往往要慢得多，因为fibonacci堆上的常数因子要高得多。这是由于许多因素（大量的指针杂耍、许多位置不佳的链接结构等）造成的，因此如果您的目标是获得尽可能快的挂钟速度，那么您可能只需要使用一个普通的旧二进制堆。即使你真的想使用Fibonacci堆，你也可以尝试优化我发布的实现——我写它的目的是为了正确性和清晰性，而不是原始效率。

关于java - 将现有的Fibonacci堆Java实现与Dijkstra的最短路径Java实现一起使用，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35708832/