使用现有的Fibonacci Heap Java实现与Dijkstra的最短路径Java实现 [英] Using Existing Fibonacci Heap Java Implementation with Dijkstra's Shortest Path Java Implementation

问题描述

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

Using java programming language, I am trying to implement the most efficient shortest path algorithm on a graph with positive edge cost. To the best of my knowledge, that would be Dijkstra's algorithm with a Fibonacci Heap as the priority Queue. I borrowed the following Fibonacci Heap implementation by Keith Schwarz as stated in the link. http://keithschwarz.com/interesting/code/?dir=fibonacci-heap

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

In my code, I also modified the dijkstra algorithm implementation presented in this question,

< a href =https://stackoverflow.com/questions/15392289/java-using-a-fibonacci-heap-for-implementing-dijkstras-algorithm> Java：使用Fibonacci堆实现Dijkstra算法

根据我的实现，这是我更新的dijkstra，

Here's my updated dijkstra based on my implementation,

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类，

Here's my Node, and AdjacentNode classes,

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

一切顺利，直到我想减少密钥以下行，

Everything went fine until i wanted to decrease the key in the following line,

myHeap.decreaseKey(vEntry, v.d); 

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

The problem I am facing is that vEntry should be an already existing node in the heap. However, I am not able to retrieve this node from the heap, since the only way I can think about to retrieve the adjacent node v is by using the adjacents list in the node u. But then, I incorrectly represent it as a new Entry Node in the following line,

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

然而，这会创建一个包含我正在寻找的节点的新条目，而不是存在的条目与我正在寻找的节点的堆。这会导致Null指针异常，如预期的那样。

This however would create a new Entry holding the node I am looking for, not the entry that exists in the heap with the node I am looking for. This results in Null pointer exception as expected.

我无法找到解决此问题的方法。获取与给定节点条目相邻的节点条目似乎不可能用于此堆实现吗？有人可以帮忙吗？谢谢。

I am not able to figure out the solution to this problem. Is it that getting a node entry which is adjacent to a given node entry seems not possible for this heap implementation? Can someone help? Thank you.

推荐答案

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

So... that's my code. :-) I figure I could probably help out here.

如果你注意到， enqueue 方法返回返回条目< T> ，表示Fibonacci堆中与您刚刚入队的对象相对应的内部条目。目的是，当你将某些内容排入Fibonacci堆中时，你将保存条目< T> ，你会回到某个地方，以便以后可以使用它。我实际上也在我的网站上实施Dijkstra算法。我做这项工作的方法是将第二个 Map 从节点存储到 Entry 对象，这样当我需要时调用 decreaseKey ，我可以查找与给定节点对应的 Entry ，然后将其传递给 decreaseKey 。

If you'll notice, the enqueue method returns back an Entry<T> representing the internal entry in the Fibonacci heap corresponding to the object you just enqueued. The intent is that, when you enqueue something into the Fibonacci heap, that you'll save the Entry<T> you get back somewhere so that you can then use it later. I actually also have an implementation of Dijkstra's algorithm up on my site. The way that I made this work was to store a second Map from nodes to Entry objects so that when I need to call decreaseKey, I can look up the Entry corresponding to the given node and then pass that into decreaseKey.

作为单挑，Dijkstra的算法与Fibonacci堆理论上的 比使用类似普通二进制堆的东西，在实践中它往往会慢得多，因为Fibonacci堆上的常数因子要高得多。这是由于许多因素（大量的指针玩杂耍，许多链接结构与当地不良等），所以如果你的目标是获得最快的挂钟速度，你可能只想使用一个普通的老式二进制堆。即使你确实想要使用Fibonacci堆，你也可以尝试优化我发布的实现 - 我写的是正确性和清晰度而不是原始效率。

As a heads-up, while Dijkstra's algorithm with a Fibonacci heap is in theory faster than using something like a plain binary heap, in practice it tends to be a lot slower because the constant factors on the Fibonacci heap are so much higher. This is due to a number of factors (tons of pointer juggling, lots of linked structures with poor locality, etc.), so if your goal is to get the fastest possible wall-clock speed, you may want to just use a plain old binary heap. Even if you do want to go with a Fibonacci heap, you may want to try optimizing the implementation I've posted - I wrote it with the goal of correctness and clarity rather than raw efficiency.

这篇关于使用现有的Fibonacci Heap Java实现与Dijkstra的最短路径Java实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！