4.4   Shortest Paths



Shortest paths.

An edge-weighted digraph is a digraph where we associate weights or costs with each edge. A shortest path from vertex s to vertex t is a directed path from s to t with the property that no other such path has a lower weight.

Shortest path

Properties.

We summarize several important properties and assumptions.

Edge-weighted digraph data type.

We represent the weighted edges using the following API:

API for a weighted directed edge


The from() and to() methods are useful for accessing the edge's vertices. DirectedEdge.java implements this API.

We represent edge-weighted digraphs using the following API:

API for an
edge-weighted graph


EdgeWeightedDigraph.java implements the API using the adjacency-lists representation.

edge-weighted digraph representation


Shortest paths API.

We use the following API for computing the shortest paths of an edge-weighted digraph:

API for SP implementations


We prepare some test data:

Data structures for single-source shortest paths.

Given an edge-weighted digraph and a designated vertex s, a shortest-paths tree (SPT) is a subgraph containing s and all the vertices reachable from s that forms a directed tree rooted at s such that every tree path is a shortest path in the digraph.

We represent the shortest paths with two vertex-indexed arrays:

Shortest paths tree

Relaxation.

Our shortest-paths implementations are based on an operation known as relaxation. We initialize distTo[s] to 0 and distTo[v] to infinity for all other vertices v.

Dijkstra's algorithm.

Dijkstra's algorithm initializing dist[s] to 0 and all other distTo[] entries to positive infinity. Then, it repeatedly relaxes and adds to the tree a non-tree vertex with the lowest distTo[] value, continuing until all vertices are on the tree or no non-tree vertex has a finite distTo[] value.

DijkstraSP.java is an efficient implementation of Dijkstra's algorithm. It uses IndexMinPQ.java for the priority queue.

Proposition.

Dijkstra's algorithm solves the single-source shortest-paths problem in edge-weighted digraphs with nonnegative weights using extra space proportional to V and time proportional to E log V (in the worst case).

Acyclic edge-weighted digraphs.

We use the term edge-weighted DAG to refer to an acyclic edge-weighted digraph.

Proposition.

By relaxing vertices in topological order, we can solve the single-source shortest-paths and longest-paths problems for edge-weighted DAGs in time proportional to E + V.

Shortest paths in general edge-weighted digraphs.

We can solve shortest path problems if (i) all weights are nonnegative or (ii) there are no cycles.

Proposition.

There exists a shortest path from s to v in an edge-weighted digraph if and only if there exists at least one directed path from s to v and no vertex on any directed path from s to v is on a negative cycle.

Proposition.

The Bellman-Ford algorithm solves the single-source shortest-paths problem from a given source s (or finds a negative cycle reachable from s) for any edge-weighted digraph with V vertices and E edges, in time proportional to E V and extra space proportional to V, in the worst case.

Q + A

Q. Does Dijkstra's algorithm work with negative weights?

A. Yes and no. There are two shortest paths algorithms known as Dijkstra's algorithm, depending on whether a vertex can be enqueued on the priority queue more than once. When the weights are nonnegative, the two versions coincide (as no vertex will be enqueued more than once). The version implemented in DijkstraSP.java (which allows a vertex to be enqueued more than once) is correct in the presence of negative edge weights (but no negative cycles) but its running time is exponential in the worst case. (We note that DijkstraSP.java throws an exception if the edge-weighted digraph has an edge with a negative weight, so that a programmer is not surprised by this exponential behavior.) If we modify DijkstraSP.java so that a vertex cannot be enqueued more than once (e.g., using a marked[] array to mark those vertices that have been relaxed), then the algorithm is guaranteed to run in E log V time but it may yield incorrect results when there are edges with negative weights.


Exercises

  1. True or false. Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.

    Solution. False.

  2. Provide an implementation of toString() for EdgeWeightedDigraph.java.
  3. Use the memory-cost model of Section 1.4 to determine the amount of memory used by EdgeWeightedDigraph.java to represent a graph with V vertices and E edges.

    Solution. 56 + 40V + 72E. MemoryOfEdgeWeightedDigraph.java computes it empirically assuming that no Integer values are cached—Java typically caches the integers -128 to 127.

  4. Adapt the DirectedCycle and Topological classes from Section 4.2 to use the EdgeweightedDigraph and DirectedEdge APIs of this section, thus implementing EdgeWeightedDirectedCycle.java and Topological.java.
  5. Suppose that we convert an EdgeWeightedGraph into an EdgeWeightedDigraph by creating two DirectedEdge objects in the EdgeWeightedDigraph (one in each direction) for each Edge in the EdgeWeightedGraph and then use the Bellman-Ford algorithm. Explain why this approach fails spectacularly.

    Solution: This can introduce negative cost cycles even if the edge-weighted graph does not contain them.

  6. What happens if you allow a vertex to be enqueued more than once in the same pass in the Bellman-Ford algorithm?

    Answer: The running time of the algorithm can go exponential. For example, consider what happens for the complete edge-weighted digraph whose edge weights are all -1.

Creative Problems

  1. Longest paths in DAGs. Develop an implementation AcyclicLP.java that can solve the longest-paths problem in edge-weighted DAGs.

  2. All-pairs shortest paths on a line. Given a weighted line-graph (undirected connected graph, all vertices of degree 2, except two endpoints which have degree 1), devise an algorithm that preprocesses the graph in linear time and can return the distance of the shortest path between any two vertices in constant time.

    Partial solution. Find a vertex s of degree 1 and run breadth-first (or depth-first) search to find the order in which the remaining vertices appear. Then, compute the length of the shortest path from s to v for each vertex v, say dist[v]. The shortest path between v and w is |dist[v] - dist[w]|.

  3. Monotonic shortest path. Given an edge-weighted digraph, find a monotonic shortest path from s to every other vertex. A path is monotonic if the weight of every edge on the path is either strictly increasing or strictly decreasing.

    Partial solution: relax edges in ascending order and find a best path; then relax edges in descending order and find a best path.

  4. Lazy implementation of Dijkstra's algorithm. Develop an implementation LazyDijkstraSP.java of the lazy version of Dijkstra's algorithm that is described in the text.
  5. Bellman-Ford queue never empties. Show that if there is a negative cycle reachable from the source in the queue-based implementation of the Bellman-Ford algorithm, then the queue never empties.

    Solution: Consider a negative cylce and suppose that distTo[w] <= distTo[v] + length(v, w) for all edges on cycle W. Summing up this inequality for all edges on the cycle implies that the length of the cyclie is nonnegative.

  6. Bellman-Ford negative cycle detection. Show that if any edge is relaxed during the Vth pass of the generic Bellman-Ford algorithm, then the edgeTo[] array has a directed cycle and any such cycle is a negative cycle.

    Solution: todo.

Web Exercises

  1. Optimal substructure property. Prove that every subpath on a shortest path from v to w is also a shortest path between the two endpoints.
  2. Unique shortest path tree. Suppose that there is a unique shortest path from s to every other vertex. Prove that the SPT is unique.
  3. No negative cycles. Prove that if the generic algorithm terminates, then there are no negative cycles reachable from s. Hint: upon termination, all edges reachable from s satisfy distTo[w] <= distTo[v] + e.weight(). Add up this inequality for all edges along a cycle.
  4. Predecessor graph. True or false. During execution of Bellman-Ford in an edge-weighted digraph with no negative cycles, following the edgeTo[] array always yields a path back to s. Repeat the question for Dijkstra's algorithm.
  5. Yen's improvement to Bellman-Ford. [reference] Partition the edges into two DAGs A and B: A consists of edges that go from a lower indexed vertex to a higher indexed vertex; B consists of edges that go from a higher indexed vertex to a lower indexed vertex. When iterating through all of the edges in a phase of Bellman-Ford, first iterate through the edges in A in ascending order of vertex number (a topological order of A), then iterate through the edges in B in descending order of vertex number (a topological order of B). When iterating through the edges in A, any path in the SPT that starts at a vertex with the correct distTo[] value and uses only edges in A results in the correct distTo[] value; similarly for B. The number of passes needed is the maximum number of A-B alternations on a path, which is at most (V+1)/2. Thus, the number of passes is at most (V+1)/2 instead of V.

  6. Replacement paths. Given an edge-weighted digraph with nonnegative weights and source s and sink t, design an algorithm to find the shortest path from s to t that does not use edge e for every edge e. The order of growth of your algorithm should be E V log V.

  7. Road network data sets.

    • From the DIMACS challenge. Here are all the roads in each state.

    • rome99.txt is a large portion of the directed road network of Rome from the DIMACS challenge. The graph contains 3353 vertices and 8870 edges. Vertices correspond to intersections between roads and edges correspond to roads or road segments. The edge weights are distances in meters.

    • NYC.txt is the undirected road network of New York City. The graph contains 264346 vertices and 733846 edges. It is connected, contains parallel edges, but no self-loops. The edge weights are travel times and are strictly positive.

  8. Internet routing. OSPF (Open Shortest Path First) is a widely used protocol for Internet routing that uses Dijkstra's algorithm. RIP (Routing Information Protocol) is another routing protocol based on the Bellman-Ford algorithm.
  9. Shortest path with the ability to skip one edge. Given an edge-weighted digraph with nonnegative weights, Design an E log V algorithm for finding the shortest path from s to t where you have the option to change the weight of any one edge to 0.

    Solution 1. Compute the shortest path from s to every other vertex; compute the shortest path from every vertex to t. For each edge e = (v, w), compute the sum of the length of the shortest path from s to v and the length of the shortest path from w to t. The smallest such sum provides the shortest such path.

    Solution 2.: create a digraph with two disjoint copies of each vertex and edge. For each edge v->w in the original digraph add an edge of 0 weight from v' to w''. Moving from the first copy to the second copy represents the ability to turn the weight of an edge to 0 (and this can be done only once).

  10. Floyd-Warshall algorithm. FloydWarshall.java implements the Floyd-Warshall algorithm for the all-pairs shortest path problem. It takes time proportional to V^3 and space proportional to V^2. It uses AdjMatrixEdgeWeightedDigraph.java.
  11. Randomized Bellman-Ford. [reference] Suppose that we choose the vertex order in Yen's algorithm uniformly at randomly (where A contains all the edges that go from a lower vertex in the permutation to a higher vertex). Prove that the expected number of passes is at most (V+1)/3.