Java: использование кучи Фибоначчи для реализации алгоритма Дейкстры

Question

Новое здесь, но в течение некоторого времени скрывалось как гость:)

Итак, я пытался сделать алгоритм кратчайшего пути Дейкстры, используя кучу Фибоначчи (в Java). После некоторых поисков мне удалось наткнуться на две готовые реализации, представляющие кучу Фибоначчи. Первая реализация довольно красиво сделана и может быть найдена здесь. Вторая реализация, казалось бы, менее элегантная, здесь.

Теперь все это выглядит красиво и хорошо. Тем не менее, я хочу использовать одну из этих реализаций для моей версии алгоритма Дейкстры, но мне еще не повезло с этим. Реализация Дейкстры в использовании заключается в следующем:

public void dijkstra(Vertex source) {
    {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vertexQueue.remove(v);
                    v.minDistance = distanceThroughU;
                    v.previous = u;
                    vertexQueue.add(v);
                }
            }
        }
    }
}

Ясно, что в этой реализации используется класс PriorityQueue на основе Java (который, я считаю, основан на самой двоичной куче). Я хочу изменить приведенный выше код, чтобы он использовал одну из вышеупомянутых реализаций кучи Фибоначчи вместо PriorityQueue в Java.

Я много пробовал, но просто не могу понять, как это сделать, хотя уверен, что это так же просто, как заменить несколько строк кода.

Я надеюсь, что я достаточно ясно. Это буквально мой первый пост на этих досках.

Любая помощь будет принята с благодарностью.

РЕДАКТИРОВАТЬ: В ответ на комментарии, я решил расширить свой пост с одним из моих сценариев попыток.

Вот модифицированная версия вышеупомянутого метода Дейкстры с использованием второй реализации кучи Фибоначчи, связанной ранее:

public static void computePathsFibonacciHeap(Node source) {
    {
        source.minDistance = 0.;
        FibonacciHeap myHeap = new FibonacciHeap();
        myHeap.insert(source, source.minDistance);

        while (!myHeap.isEmpty()) {
            Node u = myHeap.min();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Node v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    v.minDistance = distanceThroughU;
                    myHeap.decreaseKey(v, v.minDistance);
                    v.previous = u;
                }
            }
        }
    }
}

Это в значительной степени конвертируется непосредственно из псевдокода (поэтому вполне возможно, что я просто не правильно его перевел). Ошибка, которую я получаю, говорит: "lowerKey() получил большее значение". Если я пытаюсь удалить минимум, я получаю исключение NullPointerException.

Я уверен, что делаю что-то не так, и я хотел бы знать, что это такое. Еще раз, это использует вторую реализацию FHeap. Я бы предпочел сделать это, используя первую реализацию (это выглядит намного более тщательно / профессионально), но я, к сожалению, не мог понять, как это сделать.

Answer 1

Кажется, вам не хватает добавить все узлы в вашу кучу с Double.POSITIVE_INFINITY (кроме исходного узла с расстоянием 0,0). Вот почему у вас есть исключения NullPointerException, их просто нет в куче.

Я провел несколько тестов на нескольких реализациях Fibonacci Heap с открытым исходным кодом. Вы можете найти сам тест здесь: Experimenting-with-dijkstras-алгоритма. Также это моя версия Приоритетной очереди алгоритма Dijsktra: PriorityQueueDijkstra.java

Answer 2

The JDK does not provide an implementation of the Fibonacci Heap. You will have to create your own implementation, or you can find one in this post: Fibonacci Heap

All you have to afterwards is replacing

PriorityQueue<Vertex> vertexQueue = new PriorityQueue<>();

от

 FibonacciHeap<Vertex> vertexQueue = new FibonacciHeap<>();

Then simply change the calls to thepoll, add а также remove methods with their equivalent in your provided implementation.

Answer 3

Я работал с этим алгоритмом сам. Над функцией limitKey есть комментарий, который объясняет поведение.

Уменьшает ключ указанного элемента до нового приоритета. Если новый приоритет больше старого, эта функция генерирует исключение IllegalArgumentException. Новый приоритет должен быть конечным двойным, поэтому вы не можете установить приоритет NaN или +/- бесконечность. Это также вызывает исключение IllegalArgumentException. Предполагается, что запись принадлежит этой куче. По соображениям эффективности, это не проверяется во время выполнения.

Что касается реализации, я думаю, что вы хотели бы использовать myHeap.dequeueMin(). GetValue() вместо myHeap.min (). Разница в том, что dequeueMin () работает как poll() и удаляет его из кучи после нахождения.

И вместо myHeap.decreaseKey(v, v.minDistance) просто добавьте его, например, myHeap.insert (v, v.minDistance).