COMP 130 Elements of Algorithms and Computation
Spring 2012

[Rice University]

Priority Queues in Dijkstra's Shortest Path Algorithm

We previously described Dijkstra's Algorithm (pseudo-code) for finding the shortest path in a graph when the graph has edge distances. When outlining its implementation, we introduced the need for a priority queue. Today, we will see two implementations for priority queues, and outline the bigger picture.

Dijkstra's algorithm needs a priority queue to find the next node to explore. Nodes are added to the priority queue with their currently-known total distance — their distance acts as their“priority”. A node's priority can later be updated with a new total distance if we find a shorter path to the node. We also want to be able to find-and-remove the node with the lowest total distance, when Dijkstra's algorithm determines that the node's currently-known total distance must be its best-possible total distance.

So, in short, we need to add, update, and remove nodes and priorities. The expected behavior of adding and removing is pretty straightforward. However, there is a design decision to make for updating. I can see three reasonable options:

The second option adds unnecessary complexity. Either the first or third could be argued as being the conceptually simplest. We'll use the third, as it puts the complexity, the burden of knowing whether a node is already in the priority queue, upon the code that implements the data structure, rather on Dijkstra's algorithm.

Observation:  Notice in our functional breakdown of the Dijkstra problem, that we can can discuss portions of the algorithm in isolation, solving them as disconnected problems.  This enables us to tackle much smaller problems and to test those partial solutions so that when we integrate them into the larger whole, we will be much more confident in the integrity of that part of the algorithm.     Also, when the problems get too large for a single person to handle, breaking down the problem in to such decoupled pieces allows separate developer teams or individuals to work on different aspects of the problem with minimal coordination or interference.

In the following discussions, pay more attention to the type of questions that are asked about the problem and the type of observations noted than the specifics of this problem.    Aside from its technological importance, Dijkstra's algorithm is just an example for how one decomposes problems.

 

Decomposition by Separation of Operations

Let's look at what is required to implement our third option above.  There are some things to note:

  1. The described process above requires knowledge of a node and a distance, i.e. must be aware of a graphs.
  2. None of our priority queue implementations actually holds the node objects
    1. The queues only hold references to the node objects.
    2. The priority is a problem however because it is a primitive data type (an integer) not an object.    Thus the implementations discussed hold copies of the priority values
  3. There are two distinct operations involved:
    1. Updating the priority of (distance to) a node
    2. Updating an existing or adding a new node to the priority queue

Some thoughts about the above observations (no peeking before our class discussion please!):

"""
1.  In order to include graph-awareness, we have two basic options:  inheritance or composition:

    a.  Inheritance: Sub-class an existing class to add additional and/or specialized functionality
        i.  Sub-class OrderedGetPQ to create a graph-aware priority queue
        ii. Sub-class or create a node class that holds a priority and/or can compare against other nodes on the basis of priority
        
    b. Composition: Add functionality by creating an object that holds another object with the desired functionality, 
       i.e. is "composed" with the other object.
        i.  Create a class that is not a priority queue knows about graphs and, internally, holds a priority queue to perform those operations.
        
2. This opens up the possibility of changing the priority of a node without actually touching the priority queue

   a. A separate node-accessible node storage (e.g. a dictionary keyed by node) could be used to access the nodes to update them.   
      Mutated priorities would automatically be reflected in an OrderedGetPQ-type queue. 
   b. All the priority queue implementation work fine with mutable lists rather not just immutable tuples. Since lists are not primitive 
      data types, the queue holds references to the list.   Thus the list could be mutated outside of the queue.

3.  These operations could be separated into different parts of the system.
   
   a. This operation depends on being graph-aware and thus should be separated from any graph-unaware parts of the decomposition.
   b. This operation is graph-unaware.   The question is how this relates to a graph-unaware priority queue.  
      i. Updating a node already in the queue may be a moot issue if it is done externally to the queue.
      ii. Adding a new node could be determined either inside or outside of the node, depending on what services the queue presents 
          with regards finding nodes that it holds.    If there is an secondary node store outside of the queue, that store may offer 
          better node-finding services than the queue, which is priority-oriented, not node-oriented.  
"""

Class Discussion:   What sorts of implementations do these observations and thoughts lead to?   What are the pro's and con's of different possibilities?   

Rarely do "real" engineering problems have absolute "right" answers!

Note:  In Comp130 we cannot fully dive into all the nuances of all the decomposition issues being raised here.   These issues will be covered in subsequent classes.  For instance, the inheritance vs. compositon debate will be treated extensively in Comp310.