1

使用 java 编程语言，我试图在具有正边成本的图上实现最有效的最短路径算法。据我所知，这将是 Dijkstra 的算法，其中斐波那契堆作为优先队列。如链接中所述，我借用了 Keith Schwarz 的以下 Fibonacci Heap 实现。http://keithschwarz.com/interesting/code/?dir=fibonacci-heap

在我的代码中，我还修改了这个问题中提出的 dijkstra 算法实现，

Java：使用斐波那契堆实现 Dijkstra 算法

这是我根据我的实现更新的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();
                }
            }
        }
    }
}

这是我的 Node 和 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是使用 node 中的相邻列表u。但是，我错误地将其表示为下一行中的新入口节点，

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

然而，这将创建一个新的条目来保存我正在寻找的节点，而不是存在于堆中的条目以及我正在寻找的节点。正如预期的那样，这会导致 Null 指针异常。

我无法弄清楚这个问题的解决方案。对于这个堆实现来说，获取与给定节点条目相邻的节点条目是否是不可能的？有人可以帮忙吗？谢谢你。

4

1 回答 1

1

所以...这是我的代码。:-) 我想我可以在这里帮忙。

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

提醒一下，虽然 Dijkstra 的 Fibonacci 堆算法在理论上比使用普通二进制堆更快，但实际上它往往要慢得多，因为 Fibonacci 堆上的常数因子要高得多。这是由许多因素造成的（大量的指针杂耍、大量局部性较差的链接结构等），因此如果您的目标是获得尽可能快的挂钟速度，您可能只想使用普通的旧二进制堆。即使您确实想使用斐波那契堆，您也可能想尝试优化我发布的实现——我写它的目的是为了正确和清晰，而不是原始效率。

于 2016-02-29T20:25:34.057 回答