Graphs + Shortest Path

Graphs + Shortest Path
— print (last updated: Sep 16, 2009) — print

A directed graph, or digraph, consists of a set of vertices, V, and edges, represented by pairs (src,dest) of such vertices. The variants of this simple notion are these:

An undirected graph is one which has undirected edges, meaing that the order of the vertices in (src,dest) is irrelevant, i.e., both (src,dest) and (dest,src) are considered to be the same edge.
A weighted graph is one in which the edges (either directed or undirected) are triples containing the source, destination and a numeric value. Such edges are called weighted edges.

Our goal is to describe and write an implementation of a common algorithm for finding the shortest paths (those with least cost) in a weighted digraph from a single source vertex. This algorithm is credited to Dijkstra and it is called Dijkstra's Shortest Paths algorithm.

Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm involves a graph (directed or not) with weighted edges where the weights are non-negative. The cost of a path is the sum of the weights of the edges. Given a single source vertex, the algorithm computes a least-cost path to every other vertex which is reachable from the source.

This algorithm follows the "greedy principle" which dictates that what appears to be the best choice in a narrow sense does in fact turn out to be so. Here is a sketch of the algorithm:

Maintain a set of "known" vertices for which a minimal cost path has been determined. The set starts out as empty. All other vertices are classified as "unknown"
Maintain the set of unknown vertices with numerical values representing the cost of a path to the source through a known vertex.
Initially this set of unkown vertices has these values:
- for the source, the value is 0 (clearly)
- for all other vertices, the value is +∞
Choose an unknown vertex, v0, with a smallest value — the first time, obviously, the source vertex is chosen. The crux of the algorithm's correctness is that v0's value must be the cost of a least-cost path from the source.
After v0 is selected, add it to the known set. Then, using this additional known vertex, recompute the least-cost values for all the unknowns adjacent to v0 (none of the values of other unknowns can possibly change).
Repeat steps 4 and 5 until all vertices are known.

Analysis

Let V be the vertex set of size |V|, let E be the edge set of size |E|. There are two possible approaches:

Maintain the set of (vertex,distance) pairs as a (linked) list.
- Find the smallest distance vertex by scanning the list; the accumulated effects yields an O(|V|²) run time.
- Update the distance for each edge adjacent to the new known vertex, this is O(1) cost per edge; the accumulated effects yields an O(|E|) run time.
The total is:
```
O( |V|² + |E| ) = O(|V|²)
```
Maintain the set of (vertex,distance) pairs as a binary heap (a HeapMap).
- Initialize the heap; the cost is O(|V|) due to the fact that all but one value is +∞.
- Find the smallest distance by removing the heap top at a cost of O(log |V|); the accumulated effects yields an O(|V| * log |V|) run time.
- Update the distance for each edge adjacent to the new known vertex, at a cost of O(log(|V|)) per edge; the accumulated effects yields an O(|E| * log |V|) run time.
The total is:
```
O( |V| + |E| * log |V| ) = O( |E| * log |V| )
```

The choice of approach depends on the density of edges in the graph. A complete graph is one which has all possible edges (vertex pairs). The total number of such directed edges would be |V| * (|V| – 1), or, in order terminology, O(|V|²).

A graph (or graph family, more correctly) is said to be dense if |E| = Θ(|V|²) and is said to be sparse if |E| = O(|V|).

In the case of a dense graph, the first approach has time O(|V|²) and the second approach O(|V|² * log |V|); thus favoring the first approach.
In the case of a sparse graph, the first approach has time O(|V|²) and the second approach O(|V| * log |V|); thus favoring the second approach.

Examples

The first graph is this simple one:

source = A

For this example, the Heap has 3 states:

initial:

   (C,Infinity)
(A,0.0)
   (B,Infinity)

after removing and processing A:
```
(B,1.0)
   (C,3.0)
```
after removing and processing B:

(C,2.0)

The second graph is the example used in the textbook in Figures 9.8 and 9.20.

source = v1

DiGraph Implementation

The following digraph implementation, based on the adjacency list idea, makes use of sets and maps to keep track of vertices and edges. For simplicity, we will assume that vertices are always of String type. The Edge class is simply a pair of Strings. The derived WtEdge class adds a double weight to the Edge.

Edge classes

Create the classes:

Class Name: Edge, WtEdge
package:    graph

Then insert the following content:

Edge class: ( click to show )

WtEdge class: ( click to show )

DiGraph class

The main public interface for the Digraph class consists of these functions:

boolean addVertex(String vertex): add a vertex to the vertex set
boolean addEdge(Edge edge): add an edge to set of edges for vertex edge.src
Set<String> vertices(): all vertices
Set<Edge> neighbors(String vert): edges which have vert as source

Making WtEdge a subclass of Edge allows us to easily use this single DiGraph implementation to hold either regular or weighted edges.

Create the class:

Class Name: DiGraph
package:    graph

with the following content: ( click to show )

Shortest Path Implementation

The NetBeans project we're using is called GraphDemo. In addition to the the graph package developed in this document, we will also use the HeapMap described in the Priority Queues + HeapSort document:

Class Name: HeapMap
package:    heap

Here is the class content: ( click to show )

This is the complete Main class:

package graphdemo;

import java.util.*;
import graph.*;
import heap.HeapMap;

public class Main {
  public static void main(String[] args) {
    mainShortestPath(args);
  }

  public static void mainShortestPath(String[] args) {

    DiGraph graph = new DiGraph();

    Edge[] edges1 = new WtEdge[]{
      new WtEdge("A", "B", 1.0),
      new WtEdge("B", "C", 1.0),
      new WtEdge("A", "C", 3.0)
    };
    String source1 = "A";

    Edge[] edges2 = new WtEdge[]{
      new WtEdge("v1", "v2", 2.0),
      new WtEdge("v1", "v4", 1.0),
      new WtEdge("v2", "v4", 3.0),
      new WtEdge("v2", "v5", 10.0),
      new WtEdge("v3", "v1", 4.0),
      new WtEdge("v3", "v6", 5.0),
      new WtEdge("v4", "v3", 2.0),
      new WtEdge("v4", "v5", 2.0),
      new WtEdge("v4", "v6", 8.0),
      new WtEdge("v4", "v7", 4.0),
      new WtEdge("v5", "v7", 6.0),
      new WtEdge("v7", "v6", 1.0)
    };
    String source2 = "v1";

    Edge[] edges;
    String source;

    edges = edges1;    // or, edges2
    source = source1;  // and source2

    for (Edge edge : edges) {
      graph.addEdge(edge);
    }

    // costs from the source, every vertex registered as a key in this Map
    Map<String, Double> source_cost = new LinkedHashMap<String, Double>();

    // source_path.get(v) = list of intermediate vertices from source to v
    Map<String, List<String>> source_path = new LinkedHashMap<String, List<String>>();

    HeapMap<String, Double> heap = new HeapMap<String, Double>();

    // initialize the Heap with tentative distances from source
    heap.put(source, 0.0);
    for (String v : graph.vertices()) {
      if (!v.equals(source)) {
        heap.put(v, Double.POSITIVE_INFINITY);
      }
    }

    // path from source to source is an empty list
    source_path.put(source, new LinkedList<String>());

    while (!heap.isEmpty()) {

      heap.reverseInorderOutput();
      System.out.println("--------------------------");
      System.out.println("paths: " + source_path);
      System.out.println("costs: " + source_cost);
      System.out.println();

      // remove the least element, a vertex with tentative cost
      // from source. This distance MUST be the least cost
      Map.Entry<String, Double> dist_pair = heap.remove();

      // register the vertex's cose in source_cost, making it "known"
      String v = dist_pair.getKey();
      source_cost.put(v, dist_pair.getValue());

      // take all unknown neighbors of v and see if you can
      // lower the tentative cost by "going through v"

      for (Edge edge : graph.neighbors(v)) {

        String dest = edge.dest;

        if (source_cost.get(dest) == null) {  // if != null, dest is known

          // compute an alternative tentative least-cost as the cost
          // of going to v + the edge-weight

          double known_cost = source_cost.get(v);

          double weight = ((WtEdge) edge).weight;

          double alt_cost = known_cost + weight;

          // see if this newly computed cost is less to dest,
          // reset dest's cost, causing a "decreaseKey"
          if (alt_cost < heap.get(dest)) {

            // reset the improved least-cost value for dest

            heap.put(dest, alt_cost);

            // change the least-cost path to the path up to v, plus v
            List<String> path = new LinkedList<String>(source_path.get(v));
            path.add(v);
            source_path.put(dest, path);
          }
        }
      }
    }

    // print the results
    System.out.println("COMPLETE:");
    System.out.println(source_cost);
    System.out.println(source_path);
  }
}