使用现有的 Fibonacci 堆 Java 实现和 Dijkstra 的最短路径 Java 实现

Question

使用 java 编程语言，我试图在具有正边成本的图上实现最有效的最短路径算法。据我所知，这将是 Dijkstra 的算法，将 Fibonacci 堆作为优先队列。如 link 中所述，我借用了 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();
                }
            }
        }
    }
}

这是我的节点和 AdjacentNode 类,

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);

然而，这将创建一个新条目，其中包含我正在寻找的节点，而不是存在于堆中的条目以及我正在寻找的节点。这会按预期导致空指针异常。

我想不出解决这个问题的方法。对于这个堆实现来说，获取与给定节点条目相邻的节点条目似乎是不可能的吗？有人可以帮忙吗？谢谢。

Answer 1

所以...这就是我的代码。 :-) 我想我可能会在这里提供帮助。

如果您注意到，enqueue 方法 returns 返回一个 Entry<T> 表示斐波那契堆中与您刚入队的对象相对应的内部条目。目的是，当您将某些东西排入 Fibonacci 堆时，您将保存 Entry<T> 返回某个地方，以便以后可以使用它。实际上，我的网站上也有 an implementation of Dijkstra's algorithm。我完成这项工作的方法是将第二个 Map 从节点存储到 Entry 对象，这样当我需要调用 decreaseKey 时，我可以查找对应的 Entry到给定的节点，然后将其传递到 decreaseKey.

请注意，虽然 Dijkstra 的斐波那契堆算法在理论上比使用普通二叉堆之类的东西要快，在实践中 它往往会慢很多，因为斐波那契堆上的常数因子要高得多。这是由多种因素造成的（大量的指针杂耍、大量局部性差的链接结构等），因此如果您的目标是获得最快的挂钟速度，您可能只想使用普通的旧二进制堆。即使您确实想要使用 Fibonacci 堆，您也可能想尝试优化我发布的实现 - 我写它的目的是为了正确和清晰而不是原始效率。

使用现有的 Fibonacci 堆 Java 实现和 Dijkstra 的最短路径 Java 实现

Using Existing Fibonacci Heap Java Implementation with Dijkstra's Shortest Path Java Implementation

java

algorithm

dijkstra

shortest-path

fibonacci-heap