Какой тип данных использовать в качестве очереди в алгоритме Дейкстры? - PullRequest
17 голосов
/ 07 июня 2011

Я пытаюсь реализовать алгоритм Дейкстры в Java (самообучение). Я использую псевдокод, предоставленный Википедией ( ссылка ). Теперь ближе к концу алгоритма, я должен decrease-key v in Q;. Я думаю, я должен был реализовать Q с BinaryHeap или что-то подобное? Какой будет правильный (встроенный) тип данных для использования здесь?

private void dijkstra(int source) {
        int[] dist = new int[this.adjacencyMatrix.length];
        int[] previous = new int[this.adjacencyMatrix.length];
        Queue<Integer> q = new LinkedList<Integer>();

        for (int i = 0; i < this.adjacencyMatrix.length; i++) {
            dist[i] = this.INFINITY;
            previous[i] = this.UNDEFINED;
            q.add(i);
        }

        dist[source] = 0;

        while(!q.isEmpty()) {
            // get node with smallest dist;
            int u = 0;
            for(int i = 0; i < this.adjacencyMatrix.length; i++) {
                if(dist[i] < dist[u])
                    u = i;
            }

            // break if dist == INFINITY
            if(dist[u] == this.INFINITY) break;

            // remove u from q
            q.remove(u);

            for(int i = 0; i < this.adjacencyMatrix.length; i++) {
                if(this.adjacencyMatrix[u][i] == 1) {
                    // in a unweighted graph, this.adjacencyMatrix[u][i] always == 1;
                    int alt = dist[u] + this.adjacencyMatrix[u][i]; 
                    if(alt < dist[i]) {
                        dist[i] = alt;
                        previous[i] = u;

                        // here's where I should "decrease the key"
                    }
                }
            }
        }
    }

Ответы [ 4 ]

35 голосов
/ 07 июня 2011

Самый простой способ - использовать приоритетную очередь, а не заботиться о ранее добавленном ключе в приоритетной очереди.Это означает, что у вас будет каждый узел несколько раз в очереди, но это совсем не повредит алгоритму.Если вы посмотрите на него, все версии узла, которые были заменены, будут обнаружены позже, и к тому времени будет определено ближайшее расстояние.

Проверка if alt < dist[v]: из Википедии - это то, чтоделает эту работу.Время выполнения от этого только немного ухудшится, но если вам нужна очень быстрая версия, вам придется оптимизировать ее дальше.

ПРИМЕЧАНИЕ:

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

Самое главное: прежде чем пытаться это сделать,убедитесь, что ваша очередь приоритетов обрабатывает приоритет.Фактический приоритет в очереди никогда не должен изменяться, иначе вы можете испортить инварианты очереди, что означает, что элементы, хранящиеся в очереди, могут быть недоступны для поиска.Например, в Java приоритеты хранятся вместе с объектом, поэтому вам нужна дополнительная оболочка:

Это не будет работать:

import java.util.PriorityQueue;

// Store node information and priority together
class Node implements Comparable<Node> {
  public int prio;
  public Node(int prio) { this.prio = prio; }

  public int compareTo(Node n) {
     return Integer.compare(this.prio, n.prio);
  }
}

...
...
PriorityQueue<Node> q = new PriorityQueue<Node>();
n = new Node(10);
q.add(n)
...
// let's update the priority
n.prio = 0;
// re-add
q.add(n);
// q may be broken now

Поскольку на n.prio=0 вы также меняетеприоритет объекта в очереди.Тем не менее, это будет работать нормально:

import java.util.PriorityQueue;

// Only node information
class Node {
  // Whatever you need for your graph
  public Node() {}
}

class PrioNode {
   public Node n;
   public int prio;
   public PrioNode(Node n, int prio) {
     this.n = n;
     this.prio = prio;
   }

   public int compareTo(PrioNode p) {
      return Integer.compare(this.prio, p.prio);
   }
}

...
...
PriorityQueue<PrioNode> q = new PriorityQueue<PrioNode>();
n = new Node();
q.add(new PrioNode(n,10));
...
// let's update the priority and re-add
q.add(new PrioNode(n,0));
// Everything is fine, because we have not changed the value
// in the queue.
11 голосов
/ 24 февраля 2017

Вы можете использовать TreeSet, (в C ++ вы можете использовать std::set) для реализации своей очереди приоритетов для Dijkstra. TreeSet представляет набор, но мы также позволили описать порядок элементов в наборе . Вам нужно хранить узлы в наборе и использовать расстояния узлов для упорядочения узлов. Узел с наименьшим расстоянием будет в начале набора.

class Node {
    public int id;   // store unique id to distinguish elements in the set
    public int dist; // store distance estimates in the Node itself
    public int compareTo(Node other) {
        // TreeSet implements the Comparable interface.
        // We need tell Java how to compare two Nodes in the TreeSet.
        // For Dijstra, we want the node with the _smallest_ distance
        // to be at the front of the set.
        // If two nodes have same distance, choose node with smaller id
        if (this.dist == other.dist) {
            return Integer.valueOf(this.id).compareTo(other.id);
        } else {
            return Integer.valueOf(this.dist).compareTo(other.dist);
        }
    }
}
// ...
TreeSet<Node> nodes = new TreeSet<Node>();

Операция extract-min реализуется с помощью следующего и занимает наихудшее время O (lgn):

Node u = nodes.pollFirst();

С помощью операции клавиша уменьшения мы удаляем узел со старым ключом (старая оценка расстояния) и добавляем новый узел с меньшим ключом (новая, лучшая оценка расстояния). Обе операции занимают O (lgn) время наихудшего случая.

nodes.remove(v);
v.dist = /* some smaller key */
nodes.add(v);

Некоторые дополнительные заметки:

  • Вышеуказанное очень просто реализовать, и, поскольку обе эти операции являются логарифмическими по n, в целом время выполнения будет O ((n + e) ​​lgn). Это считается эффективным для базовой реализации Дейкстры. См. CLRS книгу ( ISBN: 978-0-262-03384-8 ) Глава 19 для доказательства этой сложности.
  • Хотя большинство учебников будут использовать очередь приоритетов для Dijkstra, Prim, A * и т. Д., К сожалению, ни в Java, ни в C ++ на самом деле нет реализации очереди приоритетов с той же операцией уменьшения клавиши O (lgn)!

  • PriorityQueue существует в Java, но метод remove(Object o) является , а не логарифмическим, и поэтому ваша операция нажатия клавиши будет O (n) вместо O (lgn) и ( асимптотически) вы получите более медленный Dikjstra!

  • Чтобы создать TreeSet из ничего (используя цикл for), требуется время O (nlgn), которое немного медленнее, чем время O (n) в худшем случае, для инициализации очереди кучи / приоритета из п предметов. Однако основной цикл Dijkstra занимает время O (nlgn + elgn), которое доминирует в этом времени инициализации. Так что для Дейкстры инициализация TreeSet не вызовет существенного замедления.

  • Мы не можем использовать HashSet, потому что мы заботимся о порядке ключей - мы хотим быть в состоянии вытащить сначала самые маленькие. Это дает нам узел с наилучшей оценкой расстояния!

  • TreeSet в Java реализован с использованием красно-черного дерева - самобалансирующегося бинарного дерева поиска. Вот почему эти операции имеют логарифмическое наихудшее время.

  • Вы используете int s для представления своих узлов графа, что хорошо, но когда вы вводите класс Node, вам понадобится способ связать две сущности. Я бы порекомендовал создать HashMap<Integer, Node> при построении графика - это поможет отследить, какой int соответствует тому, что Node. `

4 голосов
/ 07 июня 2011

Рекомендованный PriorityQueue не обеспечивает операцию нажатия клавиши. Однако его можно эмулировать, удалив элемент, а затем вставив его заново с новым ключом. Это не должно увеличивать асимптотическое время выполнения алгоритма, хотя его можно сделать немного быстрее с помощью встроенной поддержки.

РЕДАКТИРОВАТЬ : Это увеличивает время асимптотического запуска, поскольку ожидается, что клавиша уменьшения будет O(log n) для кучи, но remove(Object) равно O(n). Похоже, в Java нет встроенной очереди приоритетов с поддержкой эффективного ключа уменьшения.

2 голосов
/ 07 июня 2011

Очередь приоритетов согласно статье в вики. Что говорит о том, что классическая реализация сейчас заключается в использовании «очереди с минимальным приоритетом, реализованной кучей Фибоначчи».

...