Module 8: Graphs, Part II

Single-source?

• Typically, we are interested in the shortest path from vertex i to vertex j for every pair i, j.

• In the single-source version: we want the shortest path from a given vertex s to every other vertex.

• Why single-source?
  Because of the shortest path containment property:
  • Suppose the shortest path from i to j goes through k.
  • Then, the part of the path up to k is a shortest path to k.

    

    If not, we would be able to create a shorter path to j.

• An implication of the containment property:
  • If all edge weights are unique, the group of paths from a source form a tree.

    

  • If edge weights are not unique, there exists a tree with equivalent paths (to the group of paths).

• Thus, given a source, we can find a shortest-path tree rooted at the source.

Key ideas in algorithm:

• Start at source vertex and grow tree in steps.

• At each step identify edges going out from tree to non-tree vertices.

• Pick "best" such vertex and add it to tree (along with connecting edge).

• Consider edges leading out:

  

  
  Find the edge leading out that has the least total weight (from source s).

• Why does this work?

  

  If a shorter alternate path existed, it would contradict the selection of the current path.

Example:

• We'll find the Shortest Path Tree (SPT) rooted at vertex 0 (the source).

  

  
  ⇒ find shortest path from 0 to each vertex i.

• Current SPT contains vertex 0.

• Explore edges from most recently-added vertex (vertex 0):

  

• Select vertex (outside SPT) with least weight (vertex 1), add it, and explore its edges:

  

• Note:
  • We associate with each vertex the total (currently-known) weight to the vertex from vertex 0.
  • Let's call this value the "priority" of a vertex.

• Add vertex with lowest "priority" value (vertex 3) and explore its edges:

  

• Next vertex: 2

  

• Continuing, we add: 4, 6, 5 and 7:

  

In-Class Exercise 8.12: Find the shortest path tree rooted at vertex 1 in this graph:

Implementation:

• Key ideas:
  • Again (as in Prim's MST algorithm), we associate a priority with each vertex.
  • priority[i] = currently-known least-weight to i from source.
  • Note: priorities change as vertices are processed
    ⇒ need decreaseKey operation.
  • Use priority queue with extractMin and decreaseKey.

• High-level pseudocode:

  
  Algorithm: Dijkstra-SPT (G, s)
  Input: Graph G=(V,E) with edge weights and designated source vertex s.
  
       // Initialize priorities and place in priority queue. 
  1.   Set priority[i] = infinity for each vertex i;
  2.   Insert vertices and priorities into priorityQueue;
  
       // Source s has priority 0 and is placed in SPT 
  3.   priorityQueue.decreaseKey (s, 0)
  4.   Add s to SPT;
  
       // Now process vertices one by one in order of priority (which 
       // may change during processing) 
  5.   while priorityQueue.notEmpty()
           // Get "best" vertex out of queue. 
  6.       v = priorityQueue.extractMin()
           // Place in current SPT. 
  6.       Add v to SPT;
           // Explore edges from v. 
  7.       for each neighbor u of v
  8.           w = weight of edge (v, u);
               // If there's a better way  to get to u (via v), then update. 
  9.           if priority[u] > priority[v] + w
  10.              priorityQueue.decreaseKey (u, priority[v] + w)
  11.          endif
  12.      endfor
  13.  endwhile
  
  14.  Build SPT;
  15.  return SPT
  
  Output: Shortest Path Tree (SPT) rooted at s.
    

• Details left out:
  • Initializing of priority queue.
  • Graph representation.
  • Building SPT.
    To build, we'll record predecessor vertices (as we did for MST problem).

• More detailed pseudocode: (adjacency matrix)

  
  Algorithm: Dijkstra-SPT (adjMatrix, s)
  Input: Adjacency matrix representation of graph, and designated source vertex s.
  
       // Initialize priorities and place in priority queue. 
  1.   for i=0 to numVertices-1
  2.     priority[i] = infinity
  3.     insert (vertex i,  priority[i])
  4.   endfor
  
       // Source s has priority 0 and is placed in SPT 
  5.   priorityQueue.decreaseKey (s, 0)
  4.   predecessor[s] = s
  
       // Now process vertices one by one in order of priority.
  5.   while priorityQueue.notEmpty()
           // Get "best" vertex out of queue and place in SPT. 
  6.       v = priorityQueue.extractMin()
  7.       Add v to SPT;
           // Explore edges from v. 
  8.       for i=0 to numVertices-1
               // If there's an edge and it's not a self-loop. 
  9.           if i != v and adjMatrix[v][i] > 0
  10               w = weight of edge (v, i);
  10.              if priority[i] > adjMatrix[v][i] + w
                       // Set new priority of neighboring vertex i to total path weight 
  11.                  priorityQueue.decreaseKey (i, adjMatrix[v][i] + w)
  12.                  predecessor[i] = v
  13.              endif
  14.          endif
  15.      endfor
  16.  endwhile
  
  17.  treeMatrix = adjacency matrix representation of tree using predecessor array;
  18.  return treeMatrix
  
  Output: Shortest Path Tree (SPT) rooted at s.
    

• Sample Java code: (source file)

  
    public GraphPath[] singleSourceShortestPaths (int source)
    {
  
      // Create heap. Note: BinaryHeap implements the PriorityQueueAlgorithm 
      // interface (that has insert, extractMin and decreaseKey operations. 
  
      PriorityQueueAlgorithm priorityQueue = new BinaryHeap (numVertices);
      priorityQueue.initialize (numVertices);
      
  
      // Place vertices in priority queue. 
  
      GraphVertex[] vertices = new GraphVertex [numVertices];
      for (int i=0; i < numVertices; i++) {
        GraphVertex vertex = new GraphVertex (i);
        vertices[i] = vertex;
        if (i != source) {
          vertex.setKey (Double.MAX_VALUE);
          predecessor[i] = -1;
        }
        else {
          vertex.setKey (0);
          predecessor[i] = i;
        }
        priorityQueue.insert (vertex);
      }
      
  
      // Now process vertices one by one in order of priority (which changes 
      // during the course of the iteration. 
  
      while (! priorityQueue.isEmpty() ) {
  
        // Extract vertex with smallest priority value. 
        GraphVertex vertex = (GraphVertex) priorityQueue.extractMin ();
  
        // For readability we'll use these shortcuts. 
        int v = vertex.vertexID;
        double v_key = vertex.getKey();
        
        // Scan neighbors in adjMatrix. 
  
        for (int i=0; i < numVertices; i++) {
  
          // Look at row adjMatrix[v][i]. 
          if ( (v != i) && (adjMatrix[v][i] > 0) ) {
  
            // We have found a neighbor: relax the edge (v,i). 
            double w = adjMatrix[v][i];
  
            // If the current priority is higher, lower it via edge (v,i). 
            if (vertices[i].getKey() > v_key + w) {
  
              // decreaseKey operation. 
              priorityQueue.decreaseKey (vertices[i], v_key+w);
  
              // Record predecessor to build SPT later. 
              predecessor[i] = v;
  
            }
  
          }
  
        } //endfor 
        
      }
      
  
      // Next, we need to build the paths.  
      // ... (not shown) ... 
  
    }
    

Analysis:

• Adjacency matrix:
  • Initializations: all are O(V).
  • There are V iterations of the while-loop.
  • Finding the lowest-priority: O(log(V)) (scan of priority array).
  • Scan of neighbors: O(V)
  • Total work in while-loop: O(V²log(V))
  • Note: just like in Prim's algorithm, a straightforward implementation (without a priority queue) takes O(V²) time.

• Adjacency list:
  • Each each is processed just once (when explored):
    ⇒ O(E) decreaseKey operations (worst-case)
    ⇒ O(E log(V)) time for all decreaseKey operations.
  • Loop is executed O(V) times
    ⇒ O(V) extractMin operations
    ⇒ O(V log(V)) cost.
  • Total time: O(E log(V)) + O(V log(V)) = O(E log(V)).

Importance of data structure (priority queue):

• The priority queue allowed us to perform extractMin and decreaseKey relatively fast.

• Implementation requires close-relationship between data structure and algorithm variables/data.
  It is possible to separate, but adds cost (artificial separation).

• Other (exotic) data structures

  Data structure	extractMin	decreaseKey	Lines of code (C++)
  Binary heap	O(log(V)) worst-case	O(log(V) worst-case	40
  Pairing heap	O(log(V)) amortized	O(1) amortized	75
  Binomial heap	O(log(V)) worst-case	O(log(V)) worst-case	84
  Fibonacci heap	O(log(V)) amortized	O(1) amortized	128
  Self-adjusting binary tree	O(log(V)) amortized	O(log(V)) amortized	128
  Relaxed heap	O(log(V)) amortized	O(1) amortized	177
  Run-relaxed heap	O(log(V)) worst-case	O(1) worst-case	357

• In practice, the binary-heap performs the best:
  • O(log(V)) for decreaseKey is an overestimate.
    ⇒ most decreaseKey's cause only a few swaps.
  • Array implementation of heap is very efficient.
  • Array implementation (inadvertently) takes advantage of system caches.

8.10   Sparse vs. Dense Graphs