Which datatype to use as queue in Dijkstra's algorithm?

Question

I'm trying to implement Dijkstra's algorithm in Java (self-study). I use the pseudo-code provided by Wikipedia (link). Now near the end of the algorithm, I should decrease-key v in Q;. I guess i should have implemented Q with a BinaryHeap or something like that? What would be the right (built-in) datatype to use here?

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

Answer 1

The simplest way is to use a priority queue and not to care about the previously added key in the priority queue. This means you will have each node multiple times in the queue, but this does not hurt the algorithm at all. If you have a look at it, all versions of the node which have been replaced will be picked up later and by then the closest distance will already have been determined.

The check if alt < dist[v]: from the wikipedia is what makes this work. The runtime will only degrade a little from this, but if you need the very fast version you have to optimize further.

NOTE:

Like any optimization, this one should be handled with care and may lead to curious and hard to find bugs (see e.g. here). For most cases, just using remove and re-insert should be fine, but the trick I mentioned here, can speed up your code a little if your Dijkstra implementation is the bottleneck.

Most importantly: Before trying this, make sure how your priority queue handles the priority. The actual priority in the queue should never change, or you may mess up invariants of the queue, which means items stored in the queue may not be retrievable any more. E.g. in Java, priorities are stored together with the object, so you do need an additional wrapper:

This will not work:

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 

Because at n.prio=0 you are also changing the priority of the object within the queue. However, this will work fine:

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. 

Answer 2

You can use a TreeSet, (in C++ you can use a std::set) to implement your priority queue for Dijkstra. A TreeSet represents a set, but we also allowed to describe order of the items in the set. You need to store the nodes in the set and use the distances of the nodes to order the nodes. The node with smallest distance will be at the beginning of the set.

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>(); 

The extract-min operation is implemented via the following and takes O(lgn) worst case time:

Node u = nodes.pollFirst(); 

With the decrease-key operation, we remove the node with the old key (the old distance estimate) and add a new node with the smaller key (the new, better distance estimate). Both operations take O(lgn) worst case time.

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

---

Some extra notes:

• The above is very simple to implement and, because both of these operations are logarithmic in n, overall, the running time will be O((n + e)lgn). This is considered efficient for a basic implemtation of Dijkstra. See the CLRS book (ISBN: 978-0-262-03384-8) Chapter 19 for a proof of this complexity.

• Although most textbooks will use a priority queue for Dijkstra, Prim, A*, etc., unfortunately neither Java nor C++ actually has a implementation of priority queue with the same O(lgn) decrease key operation!

• PriorityQueue does exist in Java, but the remove(Object o) method is not logarithmic and so your decrease-key operation would be O(n) instead of O(lgn) and (asymptotically) you'd get a slower Dikjstra!

• To build up the TreeSet from nothing (using a for loop), it takes time O(nlgn) which is a bit slower compared to the O(n) worst case time to initialise a heap / priority queue from n items. However the main loop of Dijkstra takes time O(nlgn + elgn) which dominates this initialisation time. So for Dijkstra, initialising a TreeSet won't cause any significant slowdown.

• We can't use a HashSet because we care about the order of the keys - we want to be able to pull out the smallest first. This gives us the node with the best distance estimate!

• TreeSet in Java is implemented using a Red-Black tree - a self-balancing binary search tree. That's why these operations have logarithmic worst case time.

• You're using ints to represent you graph nodes which is good but when you introduce a Node class you'll need a way to relate the two entities. I'd recommending building a HashMap<Integer, Node> when you build you graph - it'll help keep track of which int corresponds to what Node. `