Single-Source Shortest Paths with Negative Real Weights in Õ(mn8/9) Time

This paper presents a randomized algorithm for the problem of single-source shortest paths on directed graphs with real (both positive and negative) edge weights. Given an input graph with n vertices and m edges, the algorithm completes in Õ(mn 8/9 ) time with high probability. For real-weighted graphs, this result constitutes the first asymptotic improvement over the classic O(mn)-time algorithm variously attributed to Shimbel, Bellman, Ford, and Moore. w(s, u) = 0 to the graph, and finally solve SSSP from the super source s in the augmented graph. Johnson's algorithm [12] uses this same graph augmentation with S = V .

Simplifying assumptions (without loss of generality). We shall make the following assumptions about the input graph throughout. (1) If (u, v) ∈ E and w(u, v) < 0, then u has only one outgoing edge; thus, there are at most n negative-weight edges in the graph. 2 (2) Every vertex has degree at most O(m/n); thus, a subgraph on n/r vertices has O(m/r) edges. 3 These assumptions are without loss of generality as they can be obtained from an arbitrary input graph via a simple graph transformation without increasing the size of the graph by more than a constant factor and without changing distances between vertices in the original vertex set.

We shall also assume that m ≥ 2n to keep some of the statements of performance bounds more concise. A constant of at least two here also implies that the number of edges is dominated by the number of edges with nonnegative weight.

Hop-limited shortest paths. It is a simple exercise to construct a SSSP algorithm that runs in Õ(hm) time when shortest paths are limited to h ≥ 1 negative-weight edges or "hops." (Section 2 introduces corresponding notation and briefly summarizes such an algorithm.) The novel algorithm in this paper applies hop-limited SSSP as a subroutine.

As with most of the integer-weight algorithms for SSSP, the algorithm in this paper relies on price functions introduced by Johnson [12] to transform the graph to an equivalent one without negative weights; then Dijkstra's algorithm can be used to solve the SSSP problem on the reweighted graph. In more detail, a price function is a function φ : V → R. Given a price function φ, define

Modifying the weights in this way has the following key properties [12]: (1) every cycle C has the same weight in both G and G φ , so negative-weight cycles are preserved, and (2) a path p is a shortest path in G φ if and only if it is a shortest path in G. More precisely, all u-to-v paths p satisfy w φ (p) = w(p) + φ(u)φ(v); if p is a cycle then φ(u) = φ(v) and hence w φ (p) = w(p). Price functions also compose in the natural way, i.e., (w φ 1 ) φ 2 (u, v) = w φ 1 +φ 2 (u, v).

We call φ or w φ a valid reweighting if w φ does not cause any edge weights to become negative. That is, if ∀e ∈ E((w(e) ≥ 0) =⇒ (w φ (e) ≥ 0)). We say that φ or w φ eliminates a negative edge e ∈ E if w(e) < 0 and w φ (e) ≥ 0.

Johnson [12] shows that (assuming no negative-weight cycles) the problem of eliminating all negative-weight edges can be accomplished by setting φ(v) = dist(V, v). Using Bellman-Ford to solve the super-source problem, the running time is O(mn). When there are k ≪ n negative-weight edges, applying hop-limited SSSP is better, giving a running time of Õ(km).