Shortest Paths Graph Algorithms

This chapter is from the book

Algorithms in Java, Part 5: Graph Algorithms, 3rd Edition

Learn More Buy

This chapter is from the book

This chapter is from the book 

Algorithms in Java, Part 5: Graph Algorithms, 3rd Edition

Learn More Buy

21.7 Negative Weights

We now turn to the challenge of coping with negative weights in shortest-paths problems. Perhaps negative edge weights seem unlikely, given our focus through most of this chapter on intuitive examples, where weights represent distances or costs; however, we also saw in Section 21.6 that negative edge weights arise in a natural way when we reduce other problems to shortest-paths problems. Negative weights are not merely a mathematical curiosity; on the contrary, they significantly extend the applicability of the shortest-paths problems as a model for solving other problems. This potential utility is our motivation to search for efficient algorithms to solve network problems that involve negative weights.

Figure 21.26 is a small example that illustrates the effects of introducing negative weights on a network's shortest paths. Perhaps the most important effect is that when negative weights are present low-weight shortest paths tend to have more edges than higher-weight paths. For positive weights, our emphasis was on looking for shortcuts; but when negative weights are present, we seek detours that use as many edges with negative weights as we can find. This effect turns our intuition in seeking "short" paths into a liability in understanding the algorithms, so we need to suppress that line of intuition and consider the problem on a basic abstract level.

Figure 21.26. A sample network with negative edges

The relationship shown in the proof of Property 21.18 between shortest paths in networks and Hamilton paths in graphs ties in with our observation that finding paths of low weight (which we have been calling "short") is tantamount to finding paths with a high number of edges (which we might consider to be "long"). With negative weights, we are looking for long paths rather than short paths.

The first idea that suggests itself to remedy the situation is to find the smallest (most negative) edge weight, then to add the absolute value of that number to all the edge weights to transform the network into one with no negative weights. This naive approach does not work at all, because shortest paths in the new network bear little relation to shortest paths in the old one. For example, in the network illustrated in Figure 21.26, the shortest path from 4 to 2 is 4-3-5-1-2. If we add .38 to all the edge weights in the graph to make them all positive, the weight of this path grows from .20 to 1.74. But the weight of 4-2 grows from .32 to just .70, so that edge becomes the shortest path from 4 to 2. The more edges a path has, the more it is penalized by this transformation; that result, from the observation in the previous paragraph, is precisely the opposite of what we need. Even though this naive idea does not work, the goal of transforming the network into an equivalent one with no negative weights but the same shortest paths is worthy; at the end of the section, we consider an algorithm that achieves this goal.

Our shortest-paths algorithms to this point have all placed one of two restrictions on the shortest-paths problem so that they can offer an efficient solution: They either disallow cycles or disallow negative weights. Is there a less stringent restriction that we could impose on networks that contain both cycles and negative weights that would still lead to tractable shortest-paths problems? We touched on an answer to this question at the beginning of the chapter, when we had to add the restriction that paths be simple so that the problem would make sense if there were negative cycles. Should we perhaps restrict attention to networks that have no such cycles?

Shortest paths in networks with no negative cycles Given a network that may have negative edge weights but does not have any negative-weight cycles, solve one of the following problems: Find a shortest path connecting two given vertices (shortest-path problem), find shortest paths from a given vertex to all the other vertices (single-source problem), or find shortest paths connecting all pairs of vertices (all-pairs problem).

The proof of Property 21.18 leaves the door open for the possibility of efficient algorithms for solving this problem because it breaks down if we disallow negative cycles. To solve the Hamilton-path problem, we would need to be able to solve shortest-paths problems in networks that have huge numbers of negative cycles.

Moreover, many practical problems reduce precisely to the problem of finding shortest paths in networks that contain no negative cycles. We have already seen one such example.

As we noted when we first discussed the job-scheduling problem in Section 21.6, this statement implicitly assumes that our job-scheduling problems are feasible (have a solution). In practice, we would not make such an assumption, and part of our computational burden would be determining whether or not a job-scheduling-with-deadlines problem is feasible. In the construction in the proof of Property 21.19, a negative cycle in the network implies an infeasible problem, so this task corresponds to the following problem:

Negative cycle detection Does a given network have a negative cycle? If it does, find one such cycle.

On the one hand, this problem is not necessarily easy (a simple cycle-checking algorithm for digraphs does not apply); on the other hand, it is not necessarily difficult (the reduction of Property 21.16 from the Hamilton-path problem does not apply). Our first challenge will be to develop an algorithm for this task.

In the job-scheduling-with-deadlines application, negative cycles correspond to error conditions that are presumably rare, but for which we need to check. We might even develop algorithms that remove edges to break the negative cycle and iterate until there are none. In other applications, detecting negative cycles is the prime objective, as in the following example:

Arbitrage Many newspapers print tables showing conversion rates among the world's currencies (see, for example, Figure 21.27). We can view such tables as adjacency-matrix representations of complete networks. An edge s-t with weight x means that we can convert 1 unit of currency s into x units of currency t. Paths in the network specify multistep conversions. For example, if there is also an edge t-w with weight y, then the path s-t-w represents a way to convert 1 unit of currency s into xy units of currency w. We might expect xy to be equal to the weight of s-w in all cases, but such tables represent a complex dynamic system where such consistency cannot be guaranteed. If we find a case where xy is smaller than the weight of s-w, then we may be able to outsmart the system. Suppose that the weight of w-s is z and xyz > 1; the cycle s-t-w-s then gives a way to convert 1 unit of currency s into more than 1 units (xyz) of currency s. That is, we can make a 100(xyz – 1) percent profit by converting from s to t to w back to s. This situation is an example of an arbitrage opportunity that would allow us to make unlimited profits were it not for forces outside the model, such as limitations on the size of transactions. To convert this problem to a shortest-paths problem, we take the logarithm of all the numbers so that path weights correspond to adding edge weights instead of multiplying them, and then we take the negative to invert the comparison. Then the edge weights might be negative or positive, and a shortest path from s to t gives a best way of converting from currency s to currency t. The lowest-weight cycle is the best arbitrage opportunity, but any negative cycle is of interest.

Figure 21.27. Arbitrage

Can we detect negative cycles in a network or find shortest paths in networks that contain no negative cycles? The existence of efficient algorithms to solve these problems does not contradict the NP-hardness of the general problem that we proved in Property 21.18, because no reduction from the Hamilton-path problem to either problem is known. Specifically, the reduction of Property 21.18 says that what we cannot do is to craft an algorithm that can guarantee to find efficiently the lowest-weight path in any given network when negative edge weights are allowed. That problem statement is too general. But we can solve the restricted versions of the problem just mentioned, albeit not as easily as we can the other restricted versions of the problem (positive weights and acyclic networks) that we studied earlier in this chapter.

In general, as we noted in Section 21.2, Dijkstra's algorithm does not work in the presence of negative weights, even when we restrict attention to networks that contain no negative cycles. Figure 21.28 illustrates this fact. The fundamental difficulty is that the algorithm depends on examining paths in increasing order of their length. The proof that the algorithm is correct (see Property 21.2) assumes that adding an edge to a path makes that path longer.

Figure 21.28. Failure of Dijkstra's algorithm (negative weights)

Floyd's algorithm makes no such assumption and is effective even when edge weights may be negative. If there are no negative cycles, it computes shortest paths; remarkably enough, if there are negative cycles, it detects at least one of them.

The proof of Property 21.20 does not give specific information about how to find a specific negative cycle from the distances and paths matrices computed by Floyd's algorithm. We leave that task for an exercise (see Exercise 21.122).

Floyd's algorithm solves the all-pairs shortest-paths problem for graphs that contain no negative cycles (see Figure 21.29). Given the failure of Dijkstra's algorithm in networks that contain weights that could be negative, we could also use Floyd's algorithm to solve the all-pairs problem for sparse networks that contain no negative cycles, in time proportional to V³. If we have a single-source problem in such networks, then we can use this V³ solution to the all-pairs problem that, although it amounts to overkill, is the best that we have yet seen for the single-source problem. Can we develop faster algorithms for these problems—ones that achieve the running times that we achieve with Dijkstra's algorithm when edge weights are positive (E lg V for single-source shortest paths and VE lg V for all-pairs shortest paths)? We can answer this question in the affirmative for the all-pairs problem and also can bring down the worst-case cost to VE for the single-source problem, but breaking the VE barrier for the general single-source shortest-paths problem is a longstanding open problem.

Figure 21.29. Floyd's algorithm (negative weights)

The following approach, developed by R. Bellman and L. Ford in the late 1950s, provides a simple and effective basis for attacking single-source shortest-paths problems in networks that contain no negative cycles. To compute shortest paths from a vertex s, we maintain (as usual) a vertex-indexed array wt such that wt[t] contains the shortest-path length from s to t. We initialize wt[s] to 0 and all other wt entries to a large sentinel value, then compute shortest paths as follows:

Considering the network's edges in any order, relax along each edge. Make V such passes.

We use the term Bellman–Ford algorithm to refer to the generic method of making V passes through the edges, considering the edges in any order. Certain authors use the term to describe a more general method (see Exercise 21.130).

For example, in a graph represented with adjacency lists, we could implement the Bellman–Ford algorithm to find the shortest paths from a start vertex s by initializing the wt entries to a value larger than any path length and the spt entries to null references, then proceeding as follows:

wt[s] = 0;
for (i = 0; i < G.V(); i++)
  for (v = 0; v < G.V(); v++)
  {
    if (v != s && spt[v] == 0) continue;
    AdjList A = G.AdjList(v);
    for (Edge e = A.beg(); !A.end(); e = A.nxt())
     if (wt[e.w()] > wt[v] + e.wt())
     { wt[e.w()] = wt[v] + e.wt(); st[e.w()] = e; }
  }

This code exhibits the simplicity of the basic method. It is not used in practice, however, because simple modifications yield implementations that are more efficient for most graphs, as we soon see.

GraphSPT(Graph G, int s)
{ int V = G.V(), N = 0;
  wt = new double[V]; spt = new Edge[V];
  for (int v = 0; v < V; v++) wt[v] = maxWT;
  intQueue Q = new intQueue(G.E());
  wt[s] = 0.0; Q.put(s); Q.put(V);
  while (!Q.empty())
  { int v;
    while ((v = Q.get()) == V)
      { if (N++ > V) return; Q.put(V); }
    AdjList A = G.getAdjList(v);
    for (Edge e = A.beg(); !A.end(); e = A.nxt())
      { int w = e.other(v);
        double P = wt[v] + e.wt();
        if (P < wt[w])
          { wt[w] = P; Q.put(w); spt[w] = e; }
      }
  }
}

For typical graphs, examining every edge on every pass is wasteful. Indeed, we can easily determine a priori that numerous edges are not going to lead to a successful relaxation in any given pass. In fact, the only edges that could lead to a change are those emanating from a vertex whose value changed on the previous pass.

Program 21.9 is a straightforward implementation where we use a FIFO queue to hold these edges so that they are the only ones examined on each pass. Figure 21.30 shows an example of this algorithm in operation.

Figure 21.30. Bellman–Ford algorithm (with negative weights)

Program 21.9 is effective for solving the single-source shortest-paths problem in networks that arise in practice, but its worst-case performance is still proportional to VE. For dense graphs, the running time is not better than for Floyd's algorithm, which finds all shortest paths, rather than just those from a single source. For sparse graphs, the implementation of the Bellman–Ford algorithm in Program 21.9 is up to a factor of V faster than Floyd's algorithm but is nearly a factor of V slower than the worst-case running time that we can achieve with Dijkstra's algorithm for networks with no negative-weight edges (see Table 19.2).

Other variations of the Bellman–Ford algorithm have been studied, some of which are faster for the single-source problem than the FIFO-queue version in Program 21.9, but all take time proportional to at least VE in the worst case (see, for example, Exercise 21.132). The basic Bellman–Ford algorithm was developed decades ago; and, despite the dramatic strides in performance that we have seen for many other graph problems, we have not yet seen algorithms with better worst-case performance for networks with negative weights.

The Bellman–Ford algorithm is also a more efficient method than Floyd's algorithm for detecting whether a network has negative cycles.

To conclude this section, we consider the all-pairs shortest-paths problem. Can we do better than Floyd's algorithm, which runs in time proportional to V³? Using the Bellman–Ford algorithm to solve the all-pairs problem by solving the single-source problem at each vertex exposes us to a worst-case running time that is proportional to V²E. We do not consider this solution in more detail because there is a way to guarantee that we can solve the all-paths problem in time proportional to VE log V. It is based on an idea that we considered at the beginning of this section: transforming the network into a network that has only nonnegative weights and that has the same shortest-paths structure.

In fact, we have a great deal of flexibility in transforming any network to another one with different edge weights but the same shortest paths. Suppose that a vertex-indexed array wt contains an arbitrary assignment of weights to the vertices of a network G. With these weights, we define the operation of reweighting the graph as follows:

• To reweight an edge, add to that edge's weight the difference between the weights of the edge's source and destination.

• To reweight a network, reweight all of that network's edges.

  For example, the following straightforward code reweights a network, using our standard conventions:

for (v = 0; v < G.V(); v++)
  { AdjList A = G.AdjList(v);
    for (Edge e = A.beg(); !A.end(); e = A.nxt())
      e.wt() = e.wt() + wt[v] - wt[e.w()]
  }

This operation is a simple linear-time process that is well defined for all networks, regardless of the weights. Remarkably, the shortest paths in the transformed network are the same as the shortest paths in the original network.

Since paths between different pairs of vertices are reweighted differently, reweighting could affect questions that involve comparing shortest-path lengths (for example, computing the network's diameter). In such cases, we need to invert the reweighting after completing the shortest-paths computation but before using the result.

Reweighting is no help in networks with negative cycles: The operation does not change the weight of any cycle, so we cannot remove negative cycles by reweighting. But for networks with no negative cycles, we can seek to discover a set of vertex weights such that reweighting leads to edge weights that are nonnegative, no matter what the original edge weights. With nonnegative edge weights, we can then solve the all-pairs shortest-paths problem with the all-pairs version of Dijkstra's algorithm. For example, Figure 21.31 gives such an example for our sample network, and Figure 21.32 shows the shortest-paths computation with Dijkstra's algorithm on the transformed network with no negative edges. The following property shows that we can always find such a set of weights:

Figure 21.31. Reweighting a network

Figure 21.32. All shortest paths in a reweighted network

Just as we did when we used the Bellman–Ford algorithm to detect negative cycles, we have two ways to proceed to make every edge weight nonnegative in an arbitrary network with no negative cycles. Either we can begin with a source from each strongly connected component, or we can add a dummy vertex with an edge of length 0 to every network vertex. In either case, the result is a shortest-paths spanning forest that we can use to assign weights to every vertex (weight of the path from the root to the vertex in its SPT).

For example, the weight values chosen in Figure 21.31 are precisely the lengths of shortest paths from 4, so the edges in the shortest-paths tree rooted at 4 have weight 0 in the reweighted network.

In summary, we can solve the all-pairs shortest-paths problem in networks that contain negative edge weights but no negative cycles by proceeding as follows:

• Apply the Bellman–Ford algorithm to find a shortest-paths forest in the original network.

• If the algorithm detects a negative cycle, report that fact and terminate.

• Reweight the network from the forest.

• Apply the all-pairs version of Dijkstra's algorithm to the reweighted network.

After this computation, the paths matrix gives shortest paths in both networks, and the distances matrix give the path lengths in the reweighted network. This series of steps is sometimes known as Johnson's algorithm (see reference section).

To implement Johnson's algorithm, we combine the implementation of Program 21.9, the reweighting code that we gave just before Property 21.23, and the all-pairs shortest-paths implementation of Dijkstra's algorithm in Program 21.4 (or, for dense graphs, Program 20.6). As noted in the proof of Property 21.22, we have to make appropriate modifications to the Bellman–Ford algorithm for networks that are not strongly connected (see Exercises 21.135 through 21.137). To complete the implementation of the all-pairs shortest-paths interface, we can either compute the true path lengths by subtracting the weight of the start vertex and adding the weight of the destination vertex (undoing the reweighting operation for the paths) when copying the two arrays into the distances and paths matrices in Dijkstra's algorithm, or we can put that computation in dist in the ADT implementation.

For networks with no negative weights, the problem of detecting cycles is easier to solve than is the problem of computing shortest paths from a single source to all other vertices; the latter problem is easier to solve than is the problem of computing shortest paths connecting all pairs of vertices. These facts match our intuition. By contrast, the analogous facts for networks that contain negative weights are counterintuitive: The algorithms that we have discussed in this section show that, for networks that have negative weights, the best known algorithms for these three problems have similar worst-case performance characteristics. For example, it is nearly as difficult, in the worst case, to determine whether a network has a single negative cycle as it is to find all shortest paths in a network of the same size that has no negative cycles.

Exercises

• 21.109 Modify your random-network generators from Exercises 21.6 and 21.7 to generate weights between a and b (where a and b are both between – 1 and 1) by rescaling.

• 21.110 Modify your random-network generators from Exercises 21.6 and 21.7 to generate negative weights by negating a fixed percentage (whose value is supplied by the client) of the edge weights.

• 21.111 Develop client programs that use your generators from Exercises 21.109 and 21.110 to produce networks that have a large percentage of negative weights but have at most a few negative cycles, for as large a range of values of V and E as possible.

• 21.112 Find a currency-conversion table online or in a newspaper. Use it to build an arbitrage table. Note: Avoid tables that are derived (calculated) from a few values and that therefore do not give sufficiently accurate conversion information to be interesting. Extra credit: Make a killing in the money-exchange market!

• 21.113 Build a sequence of arbitrage tables using the source for conversion that you found for Exercise 21.112 (any source publishes different tables periodically). Find all the arbitrage opportunities that you can in the tables, and try to find patterns among them. For example, do opportunities persist day after day, or are they fixed quickly after they arise?

• 21.114 Develop a model for generating random arbitrage problems. Your goal is to generate tables that are as similar as possible to the tables that you used in Exercise 21.113.

• 21.115 Develop a model for generating random job-scheduling problems that include deadlines. Your goal is to generate nontrivial problems that are likely to be feasible.

• 21.116 Modify your interface and implementations from Exercise 21.101 to give clients the ability to pose and solve job-scheduling problems that include deadlines, using a reduction to the shortest-paths problem.

• 21.117 Explain why the following argument is invalid: The shortest-paths problem reduces to the difference-constraints problem by the construction used in the proof of Property 21.15, and the difference-constraints problem reduces trivially to linear programming, so, by Property 21.17, linear programming is NP-hard.

• 21.118 Does the shortest-paths problem in networks with no negative cycles reduce to the job-scheduling problem with deadlines? (Are the two problems equivalent?) Prove your answer.

• 21.119 Find the lowest-weight cycle (best arbitrage opportunity) in the example shown in Figure 21.27.

• 21.120 Prove that finding the lowest-weight cycle in a network that may have negative edge weights is NP-hard.

• 21.121 Show that Dijkstra's algorithm does work correctly for a network in which edges that leave the source are the only edges with negative weights.

• 21.122 Develop a class based on Floyd's algorithm that provides clients with the capability to test networks for the existence of negative cycles.

• 21.123 Show, in the style of Figure 21.29, the computation of all shortest paths of the network defined in Exercise 21.1, with the weights on edges 5-1 and 4-2 negated, using Floyd's algorithm.

• 21.124 Is Floyd's algorithm optimal for complete networks (networks with V² edges)? Prove your answer.

• 21.125 Show, in the style of Figures 21.30 through 21.32, the computation of all shortest paths of the network defined in Exercise 21.1, with the weights on edges 5-1 and 4-2 negated, using the Bellman–Ford algorithm.

• 21.126 Develop a class based on the Bellman–Ford algorithm that provides clients with the capability to test networks for the existence of negative cycles, using the method of starting with a source in each strongly connected component.

• 21.127 Develop a class based on the Bellman–Ford algorithm that provides clients with the capability to test networks for the existence of negative cycles, using a dummy vertex with edges to all the network vertices.

• 21.128 Give a family of graphs for which Program 21.9 takes time proportional to VE to find negative cycles.

• 21.129 Show the schedule that is computed by Program 21.9 for the job-scheduling-with-deadlines problem in Exercise 21.89.

• 21.130 Prove that the following generic algorithm solves the single-source shortest-paths problem: "Relax any edge; continue until there are no edges that can be relaxed."

• 21.131 Modify the implementation of the Bellman–Ford algorithm in Program 21.9 to use a randomized queue rather than a FIFO queue. (The result of Exercise 21.130 proves that this method is correct.)

• 21.132 Modify the implementation of the Bellman–Ford algorithm in Program 21.9 to use a deque rather than a FIFO queue such that edges are put onto the deque according to the following rule: If the edge has previously been on the deque, put it at the beginning (as in a stack); if it is being encountered for the first time, put it at the end (as in a queue).

• 21.133 Run empirical studies to compare the performance of the implementations in Exercises 21.131 and 21.132 with Program 21.9 for various general networks (see Exercises 21.109 through 21.111).

• 21.134 Modify the implementation of the Bellman–Ford algorithm in Program 21.9 to implement a method that returns the index of any vertex on any negative cycle or -1 if the network has no negative cycle. When a negative cycle is present, the method should also leave the spt array such that following links in the array in the normal way (starting with the return value) traces through the cycle.

• 21.135 Modify the implementation of the Bellman–Ford algorithm in Program 21.9 to set vertex weights as required for Johnson's algorithm, using the following method: Each time that the queue empties, scan the spt array to find a vertex whose weight is not yet set and rerun the algorithm with that vertex as source (to set the weights for all vertices in the same strong component as the new source), continuing until all strong components have been processed.

• 21.136 Develop an implementation of the all-pairs shortest-paths ADT interface for sparse networks (based on Johnson's algorithm) by making appropriate modifications to Programs 21.9 and 21.4.

• 21.137 Develop an implementation of the all-pairs shortest-paths ADT interface for dense networks (based on Johnson's algorithm) (see Exercises 21.136 and 21.43). Run empirical studies to compare your implementation with Floyd's algorithm (Program 21.5) for various general networks (see Exercises 21.109 through 21.111).

• 21.138 Add a method to your solution to Exercise 21.137 that allows a client to decrease the cost of an edge. Return a flag that indicates whether that action creates a negative cycle. If it does not, update the paths and distances matrices to reflect any new shortest paths. Your method should take time proportional to V².

• 21.139 Extend your solution to Exercise 21.138 with methods that allow clients to insert and delete edges.

• 21.140 Develop an algorithm that breaks the VE barrier for the single-source shortest-paths problem in general networks for the special case where the weights are known to be bounded in absolute value by a constant.