Algorithm Alley
by Ron Gutman

Listing One
// compute a route from origin to dest using refactored Dijkstra's algorithm.
//  (This method can be included in a class of routing utilities).
static Node route(Node origin, Node dest) 
    throws NonDecMinPQ.PQexception 
{
    // start with origin in priority queue
    NonDecMinPQ pq = new NonDecMinPQ(1000000); 
    // or use UnboundedNonDecMinPQ(10000)
    origin.cost = 0;
    pq.insert(origin);
    
    Node node = null;
    while (true) {
       node = (Node) pq.extractMin();
       node.visited = true;
       if ((node == null) || (node == dest))
           break;
       // process each link from visited node
       for (int i=0; true; i++) {
          Link link = node.getLink(i);
          if (link == null) 
             break;
          Node next = link.node;
          int cost = node.cost + link.cost;
          if (!next.visited) { 
              if (next.queued) {
                 if (cost < next.cost) {
                    // cheaper route to node
                    pq.remove(next);
                    next.cost = cost;
                    next.predecessor = node;  
                    pq.insert(next);
                 }
              }
              else {
                 next.cost = cost;
                 next.predecessor = node;
                 pq.insert(next);
              }
          }
          // else already found best route to this node, so do nothing
       }
    }  
    // if node is not null its the destination node with cost and a
    // linked list back to the origin
    return node; 
}
   

Listing Two   
// represents a link in a road network
public class Link {
    RouteNode node; //the node to which the link goes
    int cost; //the cost to reach the node from the originating node
}
public abstract class Node {
   public int id; 
   public Node (int cost, int id) {this.cost = cost; this.id = id;}

   // members used by NonDecMinPQ
   int pqKey () {return cost;}
   boolean queued = false;  
   Node pqPrev;
   Node pqNext;
   // members used by the routing algorithm
   int cost;
   Node predecessor = null;  
   boolean visited = false;
   
   // This method must be defined by a subclass. Return a link from this node
   // to another node in network. Links from a node are numbered sequentially 
   // starting at 0. Returns null when n is exceeds that node's link numbers.
   abstract Link getLink (int n);
}

Listing Three 
// Priority queue with non-decreasing minimum keys. It's an error to insert 
// an object whose key is less than a previously extracted key value.
public class NonDecMinPQ {

   int minKey;      //the last key value removed   
   Node[] priority; // array of linked lists indexed by priority
   int maxIndex;    //highest index of an initialized element of array

   public class PQexception extends java.lang.Exception {
   }
   NonDecMinPQ (int tableLen) {
      minKey = 0;
      maxIndex = -1;
      priority = new Node[tableLen];
   }
   public void insert (Node object) throws PQexception {
      int key = object.pqKey();
      int index = keyToIndex(key);
      if ( (index>=priority.length) || (key<minKey) )
         throw new PQexception(); //bad key value
      //initialize new portions of the priority table
      for (int i = maxIndex+1; i <= index; i++) 
         priority[i] = null;
      if (index > maxIndex)
         maxIndex = index;       

      object.pqNext = priority[index]; //point to previous head of list
      object.pqPrev = null; //new object at head points back to nothing
      if (priority[index] != null) 
         //point previous head back to new head
         priority[index].pqPrev = object;  
      priority[index] = object;  //point head of list to new object
      object.queued = true;
   }
   public Node extractMin () {
      int i;
      // find the next occupied priority
      for (i=minKey; ((priority[i]==null)&&(i<=maxIndex)); i++) {}
      minKey = i;
      if (i > maxIndex)
         return null;  // the PQ is empty
      // remove and return first node in list at that priority   
      Node p = priority[i];
      remove (p);
      return p;
      }
   public void remove(Node object) {
      if (!object.queued)
         return;      
      // point next object back to preceding object
      if (object.pqNext != null)
         object.pqNext.pqPrev = object.pqPrev;     
      // point preceding object forward to next
      if (object.pqPrev != null)
         object.pqPrev.pqNext = object.pqNext;       
      else {
         // point head of list forward to next object
         int key = object.pqKey();
         int index = keyToIndex(key);
         priority[index] = object.pqNext;
         }
      object.queued = false;
   }
   int keyToIndex(int key) { return key;}
}

Listing Four
// This subclass requires a much smaller priority array when the cost on 
// links is always, or almost always, small. Each element in the priority 
// array has key values that are equal modulo the array length.
public class UnboundedNonDecMinPQ extends NonDecMinPQ {
    
    UnboundedNonDecMinPQ (int tableLen) {
       super(tableLen);
    }
    public Node extractMin () {
       int i;
       boolean pqEmpty = true;
      // Scan priority array, wrapping at end; scan entire array at least once
      // and continue, if array is not empty, until minimum priority is found.
       for (i = 0; (i<priority.length) || !pqEmpty; i++) {
           int key = minKey+i;
           int index = keyToIndex(key);
           for ( Node p = priority[index];
                 p != null;
                 p = p.pqNext
               ) {
                 pqEmpty = false;
                 if (p.pqKey() <= key) {
                     minKey = key;
                     remove(p);
                     return p;
                 }  
           }
       }
    return null; 
    }
    public int keyToIndex(int key) { return key%priority.length; } 
}

Listing Five
// Nodes of this class provide priority queue key values which have been 
// scaled to reduce number of possible key values & make priority queue more 
// efficient. This class must be subclassed to define the getLink method.
public abstract class NodeScaledKey extends Node  {
   public NodeScaledKey (int cost, int id) {super(cost,id);}
   public int pqKey ()  {
      if (cost < 0x100)
         return cost;
      int exponent = 1;
      int key = cost;
      while (key >= 0x200) {
         key = key >> 1;
         exponent++;
      }
      return (exponent<<8) + (key&0xff);
   }
}





4


