Ron has six years of experience developing software and technology for mapping and routing applications at companies such as Etak, Informix, and Airflash. He can be contacted at [email protected].
To help provide motorists with driving directions, route-finding applications use shortest path algorithms that operate on a network of nodes and links (also referred to as "directed graph of vertices and edges"). Each link has some associated cost (weight); see Figure 1.
The classical algorithm for finding the shortest path from one node in a network to other nodes in that network, Dijkstra's algorithm, relies heavily on a priority queue. Like stacks or FIFO queues, priority queues are data structures into which you can insert and remove objects. But objects are always removed in an order dictated by a "key," a value stored in the object. The objects inserted into the priority queue by Dijkstra's algorithm represent the nodes in a network. The key value that governs a node's removal from the priority queue is the cost of reaching that node from the origin of the search. In Figure 1, for example, the cost to reach node D from origin A is 8. Dijkstra's algorithm explores the network outward from the origin, placing nodes into the priority queue as they are encountered and removing them in order of their cost from the origin. So the priority queue governs the order of exploration of the network outward from the origin in a way that guarantees that the cheapest route will be found before more expensive routes need to be considered.
From the point of view of a motorist, a node is a point on the road network where he must decide which way to go; a link is the stretch of road from one decision point to the next. Cost can be defined in different ways, but is typically the estimated time for a driver to reach a node from his starting point (origin). Using that kind of cost, Dijkstra's algorithm extracts nodes from the priority queue in order of driving time from the origin.
Listing One is an implementation of Dijkstra's algorithm as a Java method called route. Listing Two presents Java classes used to represent the road network. (Java might not be ideal for a real implementation where performance is critical; I use it here for its ease in representing a solution at a higher level of abstraction.) The Node class defines several members used by the route method and defines other members used by the priority queue. A more robust, but more complex, design would employ two Java interfaces with suitable methods instead of these members. For a correctness proof for Dijkstra's algorithm and general information on priority queues, see Introduction to Algorithms, Second Edition, by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein (MIT Press, 2001).
Classical priority queues include the binary heap and the Fibonacci heap (see "The Fibonacci Heap," by John Boyer, DDJ, January 1997). Using a binary heap, nodes can be placed in a priority queue in O(log(n)) time, where n is the number of nodes already in the queue, and removed in O(log(n)) time. Fibonacci heaps improve insertion, but not removal, to O(log(1)) time.
In Dijkstra's algorithm, there are O(L+N) priority queue accesses where L is the number of links and N is the number of nodes in the network, so the algorithm runs in O((L+N)log(N)) time. Using a Fibonacci heap, it runs in O(Nlog(N)) time.
Location-Based Services
If you cannot make assumptions about the data presented to the priority queue, then a binary or Fibonacci heap is a good choice. A priority queue designed specifically for computing routes in a road network can do better than a binary or Fibonacci heap.
A faster priority queue would probably be of little consequence for route computation in embedded systems such as an in-car navigation system. In such systems, routing is normally I/O bound — most of the time is spent loading relevant portions of the road network into memory from a slow device such as a CD drive.
The advent of location-based services changes things. Instead of resource-starved embedded systems, such services can run on powerful servers that serve routes to thousands of mobile users. The economics of such services become attractive when hundreds of route computations can be performed per CPU-second. To that end, I/O must be eliminated by preloading the entire road network into memory, or possibly into virtual memory. The road network in the United States requires several gigabytes of memory, unreasonably expensive for occasional use in an in-vehicle system, but not for constant use on a server. If the entire road network is preloaded into memory, then the I/O costs are eliminated and the priority queue can significantly affect the chances of dishing out hundreds of routes per second.
The implementation of Dijkstra's algorithm in Listing One differs in a significant way from Dijkstra's algorithm as described in Introduction to Algorithms (or CLR, as it is referred to). The one in CLR cannot work in either a car or location-based service because it begins by inserting all nodes in the network into the priority queue. No matter if the network is in memory, a single route computation cannot afford to process every one of the millions of nodes in a road network. Only nodes in the vicinity of the origin and destination should be looked at (or even initialized) by a single route computation. Thus, nodes must be placed into the priority queue only as they are encountered.
For the rest of this article, N is the number of nodes visited by the route method of Listing One, and K is the number of distinct key values smaller than the largest key value removed from the priority queue (the key associated with the destination node). A node is considered visited when removed from the priority queue. If the largest key value removed from the priority queue is 10,000 and the key values are integers (as in Listing One), then K=10,000.
What is it about this particular use of a priority queue that would permit a specialized algorithm to outperform classical heaps? Using Dijkstra's algorithm for route finding presents these circumstances for a priority queue to exploit:
- Every node inserted has a key equal to or greater than the key for any node previously removed. This follows from the fact that the cost associated with any given link is nonnegative.
- The number of extractions, N, is not significantly less than, and perhaps more than, K. In other words, K/N is small (you can force this to be true as needed).
- The range of possible key values is, or can be, limited.
Simple Approach
It's easy to see how a priority queue for this application can perform insertion/removal in, effectively, constant time. Route costs are normally represented as an integer number of seconds. Since no route across the U.S. takes as much as 1 million seconds of driving, you can represent all cost as integers from 0 to 1 million. You can allocate an array that holds one pointer for each of these 1 million possible cost values. That amount of memory is tiny compared to the gigabytes needed to represent the road network. Each array element represents one possible key value.
Circumstance 1 means that the extractions occur in order of increasing key values (even though insertions and extraction are intermingled). So, a simple strategy can be used by the extraction algorithm to locate the object with minimum key value: Maintain an index into the array indicating where the last extraction occurred and increment that index until the next nonempty array entry is found. The index is never decremented, so the total number of increments performed by one route computation is K. This means that if the route computed takes one hour (3600 seconds) to drive, there are about 3600 index increments in the route computation.
This strategy might be unacceptable, even where Circumstance 1 holds, if the scan for the next nonempty entry is very long. But in route computation, Circumstance 2 applies. The scan finds the array that is densely populated with nonempty entries. Though there might be a few long scans, the total number of increments is K and the average per node is K/N, a small number.
The average computation needed for an extraction is, therefore, O(K/N). This performance can be much better than a classical heap would provide. The extractions from those heaps each take O(log(n)) computing, where n is the number of nodes in the priority queue. A comparison between O(K/N) and O(log(n)) is not straightforward because they involve different, complexly correlated variables. However, n, and therefore log(n), tends to grow arbitrarily large as the exploration expands. That's because n grows roughly in proportion to the expanding boundary of the explored region. On the other hand, K/N tends to be smaller for longer route computations because N is roughly proportional to the area explored, while K is roughly proportional to the distance from the origin to the destination on the boundary of the area explored. N tends to grow with the square of K. Most likely, this simple priority indexed approach outperforms a classical heap on a route of at least moderate length.
The other operations are constant time for both the priority-indexed approach and Fibonacci heaps.
Implementation
Listing Three is an implementation of this technique as a Java class called NonDecMinPQ (short for nondecreasing minimum priority queue). The Dijkstra algorithm in Listing One is a significant refactoring of that described in CLR. This is partly because of the impracticality of inserting all nodes into the priority queue. In addition, there are differences in the interfaces to the priority queue. The methods provided to the routing algorithm by the priority queue are:
- insert, same as CLR's Insert operation.
- extractMin, same as CLR's Extract-Min operation.
- remove, given any object in the priority queue, removes it from the priority queue. No CLR equivalent.
There is no decreaseKey method analogous to the Decrease-Key operation in CLR. Instead, the routing algorithm uses insert and remove to perform an equivalent operation.
A NonDecMinPQ priority queue holds nodes in its priority array. Each element of the priority array heads a linked list of nodes that share the same key value. Since all objects in one of these lists share the same key, the extractMin method can choose any node in a list to remove and return to its caller. The fastest choice is the first node on the list. Thus, nodes are both inserted and extracted from the front of the list. It is not necessary to scan the list. Figure 2 shows the priority queue at one instant in an exploration of the network in Figure 1.
The discussion so far assumes that these three values are the same for any node:
- Cost, the cost to reach the node from the origin.
- Key, the value used to insert the node into the priority queue.
- Index, the index into the priority queue's priority array.
Indeed, in Listings One through Three, the cost to reach a node is used as the node's priority queue insertion key and the insertion key is used to index the table. But the design does not assume that any of these are the same. Each node has a pqKey method that, in Listing Two, returns its cost value. In a subclass of Node, pqKey might return some other value, most likely one computed from the cost. Similarly, NonDecMinPQ has a method, keyToIndex, which simply returns its parameter, but can be overridden in a subclass to map a key value to an index in a more complex way. Separating the three concepts will prove useful.
What's the remove method for? Each node can have multiple predecessors. A predecessor for a node X is a node with equal or lower cost and a direct link to node X. Dijkstra's algorithm can encounter each node several times, once from each predecessor. The cost to a node is computed by adding the predecessor's cost and the cost of the link to the node from the predecessor. Each time the algorithm encounters a node, the cost is recomputed and the cheapest cost is stored with the node along with a pointer to the predecessor through which that cheapest cost is achieved. Changing the cost changes the key value with which the object is stored in the priority queue, so the object must be removed from the list for one key value and inserted in another. CLR suggests a Decrease-Key operation for this. The NonDecMinPQ class supports the update with its insert and remove methods. The NonDecMinPQ's linked lists are doubly linked to support efficient removal.
The methods are carefully written to avoid initializing unused portions of the priority table.
But You're Wasting So Much Memory
In case you are nervous about using 4 MB for the priority array, there is an enhancement that reduces the size of the array considerably, letting it accommodate key values of any size. It takes advantage of another property of the data that is presented to the priority queue: The cost of any link in the network is small compared to the cost of the longest possible route. This means that nodes added to the priority queue have keys not much larger than the smallest keys in the queue.
The difference between the largest and smallest key values in the priority queue can never be more than the cost of the longest link; it's a property of the queue preserved by each operation on the queue as performed by the route method in Listing One. So you can prove it using mathematical induction. In short, when a node is inserted, the cost of the new node cannot exceed the minimum cost in the priority queue at that time by more than the cost of the link from its removed predecessor, whose cost cannot be more than the minimum cost in the queue.
I've settled on 1 million seconds for the longest possible route. The cost of a typical link is the time it takes to drive from one intersection to another, typically not more than a few hundred seconds.
So, although the priority array might have a million entries, the entries in the queue at any one time span a very limited range of key values, perhaps a range of only a few hundred entries. You can use a much smaller array by mapping key values to array indices in some dynamic way. Thinking of the array as circular helps; the array index for a given key can be the key value modulo the array length.
An array with a range of a few hours should do because, even in unpopulated areas of the road network, links that long are rare. You don't have to guarantee an absolute limit on the cost of a link. An algorithm that uses a circular array can work correctly regardless, and can be written so that only its performance depends on the link costs. If you use an array with 10,000 entries, the rare cases of link costs greater than 10,000 will not cause any problem.
In Listing Four, UnboundedNonDecMinPQ implements this idea by subclassing NonDecMinPQ and redefining the method keyToIndex. The circularity of the priority array means that one array element can hold nodes with different keys. For example, if the array length is 10,000, then key values of 4, 10004, 20004, and so on can be found at index 4 because 4 mod 10000 = 10004 mod 10000 = 20004 mod 10000 = 4. But because links of cost greater than 10,000 are rare, multiple key values at one array element will be rare.
UnboundedNonDecMinPQ also redefines extractMin so that it can scan through the list at an array element to find a node with the expected key value ignoring nodes with larger key values. This scan normally terminates at the first entry on the list because larger key values are rare.
Long-Distance Routes
You'll be happy with the performance of NonDecMinPQ (or UnboundedNonDecMinPQ) for route computation as long as K/N is small. In those circumstances, the priority queue operations burn only a modest proportion of the total CPU time. Is this relationship between K and N always true? No, but you can make it true.
You might have noticed that the value of K depends on the unit of cost, which we have assumed is one second. For routes on road networks, a unit of one second is more than adequately fine grained. No one would care whether one route is a few seconds longer or shorter than another. And the data used to compute routes is not nearly accurate enough to justify concern about seconds. Thus, you could easily change the unit of cost to five seconds. That would reduce the cost of scanning the priority array five times. It would also treat costs within five seconds of each other as equivalent — not unreasonable.
However, when using the Dijkstra algorithm as represented in Listing One, such a change of units is of dubious value in reducing computation time. That's because the number of nodes encountered by the algorithm tends to increase with the square of the distance from the origin, while the maximum cost tends to increase linearly. So as routes get longer, K/N gets smaller and the priority queue actually performs better and better as a function of N.
Yet long-distance routes do provide a motivation for changing the unit of cost. Because the number of nodes encountered becomes very large as the exploration moves away from the origin, the algorithm is modified in applications where medium- or long-distance routes are computed. The full complexity of these modifications is beyond the scope of this article, but the core idea is that any route computation performed at a large distance from the origin and destination is allowed to ignore minor roads. The farther from the origin and destination, the greater the percentage of roads that are not considered in the search. So a route computation from California to Florida, when it gets to Texas, considers only highways. As the exploration progresses, the road network is thinned out drastically, so much so that the number of nodes encountered does not increase even linearly with distance, let alone with the square of distance.
Under these circumstances:
- The priority queue can spend a large proportion of the route computation scanning the priority array. This means you want to reduce the amount of scanning after all.
- The result of the computation is an approximate one. It is not guaranteed to find the best route, though it generally finds a good one. This means you can tolerate a technique that introduces some small additional approximation.
I've already asked how small the unit of cost really needs to be to permit accurate results. But a deeper question is: How many distinct key values are really needed? The surprising answer: only a few thousand. And if only a few thousand are needed, then the priority queue would never need to scan more than a few thousand array entries in a single route computation.
Listing Five is a subclass of Node, NodeScaledKey, that redefines the pqKey method. The method computes a key as a function of the node's cost. The function, f(c) where c is the cost, has these properties:
- If a<b, then f(a)<=f(b).
- If f(a)<f(b), then a<b.
- The number of distinct values returned by f(a) for 256<a<N, is approximately 256×(log2(N)-7)
- If f(a)=f(b), then|a-b|/a<1/256.
The key value returned by f is a nonlinear function of its parameter, but, as Properties 1 and 2 state, it's a monotonically increasing function that ensures the correct functioning of Dijkstra's algorithm. That is, since comparisons between f(a) and f(b) are consistent with those between a and b, the priority queue will make the same decisions for key values of f(a) and f(b) as for key values of a and b, except when a<b and f(a)=f(b). In those cases, the priority queue will decide arbitrarily which of the two objects, with costs a and b, will be returned first by extractMin. However, Property 4 assures us that this exception will not affect the results badly; in those cases, a and b differ by less than 0.4 percent. That means that the result of the computation is a route no more than 0.4 percent longer than it would otherwise be (the algorithm is guaranteed to choose a route with minimum value for pqKey(), and the true best route must have the same value for pqKey(), and therefore, a cost at most 0.4 percent less). A 0.4 percent error might be acceptable whenever the realities of long-distance routing force you to accept much cruder approximations.
NodeScaledKey.pqKey() works by computing two values:
e=int(log2(cost)-7)
m=(cost>>(e-1)) mod 256
The two values are similar to a floating-point exponent and mantissa. Placing the exponent, e, in the high-order bits provides the monotonicity. The key value returned is (e<<8)+m.
By ignoring distinctions that are too fine to be relevant, this approach compresses the possible set of key values into such a small set that the priority queue can handle them effortlessly and with a negligible amount of memory.
Ranking
In location-based services, route finding is commonly used for ranking locations by how quickly they can be reached from an origin. For example, which gas stations can be most quickly reached from a given location? This kind of ranking involves computing many routes. Fortunately, the basic Dijkstra algorithm computes a route to each node it extracts from the priority queue, so ranking of many destinations can be accomplished by a single route computation.
The advanced optimizations for long-distance routes are difficult to apply to this ranking problem, so a reasonable approach to ranking is to use the basic Dijkstra algorithm especially if ranking destinations that are not far from the origin. In this context, any of the priority queue variations described here perform superbly.
Conclusion
Although the classical priority queues are good for the general case, the techniques described here are much more effective for route computations on road networks.
These examples show how the context in which algorithms are used can affect their design. Perhaps compression algorithms provide even better support for this thesis. There is no compression algorithm that compresses all possible data. Instead, each compression algorithm is designed to exploit the patterns in one kind of data for particular applications. Thus, you have text compression, image compression, and so on. Even Huffman compression depends on a pattern in the data — the appearance of some values with much greater frequency than others.
Acknowledgments
Thanks to those who reviewed this article and suggested valuable improvements: Koji Amakawa of Telcontar, Ilya Sandler of TeleAtlas, Stefan Schroedl of Daimler-Chrysler, Shay Gal-On of Improv Systems, and Mark Gilkey of Solid Technologies.
DDJ
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;
