Почему очередь приоритетов Java не пуста после выполнения следующего кода?

avatar
kauray
8 апреля 2018 в 04:51
171
3
-1

Я пытаюсь реализовать алгоритм Дейкстры и использую следующий код. Я использовал отладчик в Eclipse для пошагового выполнения программы и обнаружил, что он выдает правильные значения в середине выполнения. Однако после этого очередь приоритетов, которую я использовал из пакета java.util, не оказывается пустой. Хотя теоретически он должен быть пустым из следующего кода.

В отладчике видно, что очередь приоритетов содержит ссылки со значениями, установленными на бесконечность. Что за ошибка в коде?

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;


public class Dijkstra {
    static class Vertex implements Comparable<Vertex>{
        private int vertexid;
        private Double distance;

        public Vertex(int vertexid, Double distance) {
            this.vertexid = vertexid;
            this.distance = distance;
        }

        public int getVertexid() {
            return vertexid;
        }

        public Double getDistance() {
            return distance;
        }

        public int compareTo(Vertex other) {
            return this.getDistance().compareTo(other.getDistance());
        }

        public boolean equals(Object o) {
            if (o instanceof Vertex) {
                Vertex v = (Vertex) o;
                return vertexid == v.vertexid && distance == v.distance;
            }
            return false;
        }
    }

    public static void dijkstra(double g[][], int n, int m, int source) {
        // g is the adjacency matrix
        // n is the number of nodes
        // m is the number of edges

        // initialize shortest path

        double d[] = new double[n];


        for (int i = 0; i < n; i++) {
            d[i] = Double.POSITIVE_INFINITY;
        }
        d[source] = 0;

        HashMap<Integer, Double> s = new HashMap<Integer, Double>();
        PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();

        // initialize q
        for (int i = 0; i < n; i++) {
            q.add(new Vertex(i, d[i]));
        }

        Vertex u;

        while (!q.isEmpty()) {
            u = q.remove();
            //System.out.println(u.getVertexid() + "\t" + u.getDistance());
            s.put(u.getVertexid(), u.getDistance());

            for (int i = 0; i < n; i++) {
                if (i != u.getVertexid() || g[u.getVertexid()][i] != Double.POSITIVE_INFINITY) {
                    if (u.getDistance().doubleValue() + g[u.getVertexid()][i] < d[i] && s.containsKey(i) == false) {
                        q.remove(new Vertex(i, d[i]));
                        d[i] = u.getDistance().doubleValue() + g[u.getVertexid()][i];
                        q.add(new Vertex(i, d[i]));
                    }
                }
            }
        }

        /*for(double i: d){
            System.out.println(i);
        }*/

        System.out.println(Arrays.asList(s));
    }

    public static void main(String[] args) {
        double graph[][] = {{Double.POSITIVE_INFINITY, 4, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 8, Double.POSITIVE_INFINITY},
                {4, Double.POSITIVE_INFINITY, 8, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 11, Double.POSITIVE_INFINITY},
                {Double.POSITIVE_INFINITY, 8, Double.POSITIVE_INFINITY, 7, Double.POSITIVE_INFINITY, 4, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 2},
                {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 7, Double.POSITIVE_INFINITY, 9, 14, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
                {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 9, Double.POSITIVE_INFINITY, 10, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
                {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 4, 14, 10, Double.POSITIVE_INFINITY, 2, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
                {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 2, Double.POSITIVE_INFINITY, 1, 6},
                {8, 11, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 1, Double.POSITIVE_INFINITY, 7},
                {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 2, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 6, 7, Double.POSITIVE_INFINITY}
               };

        Dijkstra.dijkstra(graph, 9, 14, 0);

    }
}

Ниже приведены ссылки из отладчика:

enter image description here

И для содержимого приоритетной очереди:

enter image description here

После выполнения все значения s устанавливаются в бесконечность.

Источник
user207421
8 апреля 2018 в 05:26
0

Метод PriorityQueue.isEmpty() должен вернуть значение true, что означает, что PQ пуст по определению. Базовый массив может быть не пустым, но просмотр внутренних элементов недопустим.

krokodilko
8 апреля 2018 в 05:27
0

Этот вопрос следует задать на codereview.stackexchange.com

user207421
8 апреля 2018 в 05:31
0

@крокодилко Почему? Он не просил проверить свой код. Он спросил, почему это не работает, как ожидалось. Для этого и существует SO.

Ответы (3)

avatar
kauray
12 апреля 2018 в 17:02
0

Основная проблема заключается в

private Double distance;

В функции equals Double сравнивается с double. Следовательно, пока элементы удаляются из очереди приоритетов, они фактически не удаляются. Это можно исправить, изменив указанную выше строку на :

.
 private double distance;

Проверка выдает неверные значения в следующем фрагменте кода:

 public boolean equals(Object o) {
            if (o instanceof Vertex) {
                Vertex v = (Vertex) o;
                return vertexid == v.vertexid && distance == v.distance;
            }
            return false;
        }
avatar
MD Ruhul Amin
8 апреля 2018 в 09:07
1
// initialize q
for (int i = 0; i < n; i++) {
    q.add(new Vertex(i, d[i]));
}

На первом месте в очереди должен быть только исходный элемент. Вы не должны вставлять все бесконечные расстояния в очередь. В очереди должен быть только источник. А затем при обработке источника вы вставляете узлы, достижимые из источника, а затем обрабатываете ближайший узел среди узлов. Так работает этот алгоритм. Поэтому удалите цикл for, в котором вы вставляете все узлы в очередь. Вставьте в очередь только источник перед запуском цикла while. Пример:

    ...
    for (int i = 0; i < n; i++) {
        d[i] = Double.POSITIVE_INFINITY;
    }
    d[source] = 0;

    HashMap<Integer, Double> s = new HashMap<Integer, Double>();
    PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();

    // initialize q
    // only the source in the queue with 0 distance.

    q.add(new Vertex(source, d[source]));

    Vertex u;
    ...
    ...
kauray
8 апреля 2018 в 10:13
0

Это не то, как алгоритм инициализируется. Проверьте CLRS.

avatar
MD Ruhul Amin
8 апреля 2018 в 05:54
0

Похоже, вы на самом деле вставляете бесконечные значения в s. Ваше значение приоритета в конце концов становится пустым, но перед этим вы отправляете некоторую бесконечность в очередь, и в конечном итоге оно вставляется в карту. Для быстрого исправления вы должны проверить, является ли значение бесконечностью или нет, прежде чем вставлять его в карту. Это решило проблему.

    System.out.println(u.getVertexid() + "\t" + u.getDistance());
    if(u.getDistance() != Double.POSITIVE_INFINITY){
        s.put(u.getVertexid(), u.getDistance());
    }

Хотя коренная причина бесконечности лежит здесь:

    for (int i = 0; i < n; i++) {
        d[i] = Double.POSITIVE_INFINITY;
    }
    d[source] = 0;    

...
...
// initialize q
for (int i = 0; i < n; i++) {
    q.add(new Vertex(i, d[i]));
}

кроме d[source] все остальные элементы в очереди бесконечны. И вы вставляете это бесконечное значение без проверки.

u = q.remove();
s.put(u.getVertexid(), u.getDistance());
kauray
8 апреля 2018 в 05:58
0

Разве проверка < d[i] не гарантирует, что блок if не достигнет бесконечности?

MD Ruhul Amin
8 апреля 2018 в 06:57
0

Да, моя ошибка. Обновил ответ. Проверьте это сейчас.

MD Ruhul Amin
8 апреля 2018 в 07:00
0

Также вы можете просто разорвать цикл while, когда u.getDistance() == Double.POSITIVE_INFINITY. Потому что после этого все элементы в очереди бесконечны.

kauray
8 апреля 2018 в 07:14
0

Как может проблема бесконечности лежать там. Вот как работает алгоритм, и алгоритм продолжает вычислять правильные значения. Проблема в том, что в конце концов после вычисления правильных значений он устанавливает значение на бесконечность. Почему так происходит - главный вопрос.