Abstract
In the single-source shortest paths problem, the goal is to compute the shortest path tree from a designated source vertex in a weighted, directed graph. We present the first nearlinear-time algorithm for the problem that can also handle negative edge-weights; the runtime is O(m log8(n) log W). In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight single-source shortest paths to break through the classic ˜O(m√n log W) bound from more than three decades ago (Gabow and Tarjan SICOMP’89).
1. Introduction
We consider the single-source shortest paths (SSSP) problem with (possibly negative) integer weights. Given an -edge -vertex directed weighted graph with integral edge weight for every edge and a source vertex , the goal is to compute a shortest path from .
Two textbook algorithms for SSSP are Bellman-Ford and Dijkstra’s algorithm. Dijkstra’s algorithm is near-linear time ( time), but restricted to nonnegative edge weights. The Bellman-Ford algorithm5,17 can handle negative weights, and only requires that there is no negative-weight cycle reachable from in ; in particular, the algorithm either returns a shortest path tree from or returns a cycle reachable from whose total weight is negative. Unfortunately, the runtime of Bellman-Ford is .
Designing faster algorithms for SSSP with negative edge weights (denoted negative-weight SSSP) is one of the most fundamental and long-standing problems in graph algorithms. In the 80s and 90s, the scaling technique led to a wave of improvements over Bellman-Ford (Gabow,18 Gabow and Tarjan,19 and Goldberg20), culminating in runtime , where is the minimum integer such that for all . In the last few years, advances in continuous optimization and dynamic algorithms have led to a new wave of improvements, which achieve faster algorithms for the more general problems of transshipment and min-cost flow, and thus imply the same bounds for negative-weight SSSP (Cohen et al.,15 Axiotis et al.,3 BLNPSSSW.9,10,11 This line of work resulted in an near-linear runtime ( time) on moderately dense graphs10 and runtime on sparse graphs.3,a This state of the art motivates two natural questions:
Can we get near-linear runtime for all graphs?
Can we achieve efficient algorithms without complex machinery?
For the second question, note that currently all state-of-the-art results for negative-weight SSSP are based on min-cost flow algorithms, and hence rely on sophisticated continuous optimization methods and a number of complex dynamic algebraic and graph algorithms (for example, Bernstein et al.,6 Chuzhoy et al.,14 Nanongkai et al.,24 and Saranurak and Wang25). It would be useful to develop simple efficient algorithms that are specifically tailored to negative-weight SSSP, and thus circumvent the complexity currently inherent in flow algorithms; the best known bound of this kind is still the classic from over three decades ago.19,20 A related question is whether it is possible to achieve efficient algorithms for the problem using combinatorial tools, or whether there are fundamental barriers that make continuous optimization necessary.
Our Result. In this paper we resolve both of the above questions for negative-weight SSSP: we present a simple combinatorial algorithm that reduces the running time all the way down to near-linear.
There exists a randomized (Las Vegas) algorithm that takes time with high probability (and in expectation) for an -edge input graph and source . It either returns a shortest path tree from or returns a negative-weight cycle.
Independent Result and Followup Work. Independently from our result, the recent major breakthrough by Chen et al.13 culminates the line of works based on continuous optimization and dynamic algorithms and achieves an almost-linear time bound of for minimum-cost flow.b This directly implies a runtime of for negative-weight shortest paths.
In this paper, we prioritize simplicity and modularity, and not optimizing the logarithmic factors. The follow-up work by Bringmann, Cassis, and Fischer12 greatly optimizes our framework to reduce the running time to There is also follow-up work by Ashvinkumar et al. showing how the framework can be applied to the parallel and distributed models of computation.1
2. Preliminaries
Throughout, we only consider graphs with integer weights. For any weighted graph , define , and
Define ; that is, is the most negative edge weight in the graph.c Given any set of edges we define . We say that a cycle in is a negative-weight cycle if . We define to be the shortest distance from to in graph ; if there is a negative-weight cycle on some -path then we define .
Consider graph and consider subsets and . We define to be the subgraph of induced by . We slightly abuse notation and denote a subgraph of as where the weight function is restricted to edges in . We define and ; that is, they are graphs where we remove vertices and edges in and respectively. We sometimes write and instead of and , respectively, for any and . We say that a subgraph of has weak diameter if for any we have that . We always let and refer to the main input graph/source of Theorem 1.
We assume throughout the paper that the main input graph satisfies the following properties:
for all (thus, ).
Every vertex in has constant out-degree.
In the full version of the paper,7 we show that using existing techniques, one can easily reduce the general case to the more restricted case of this assumption, while only incurring a polylogarithmic overhead in the running time.
Dummy Source and Negative Edges. The definitions below capture a common transformation we apply to negative weights and also allow us to formalize the number of negative edges on a shortest path. Note that most of our algorithms/definitions will not refer to the input source , but instead to a dummy source that has edges of weight 0 to every vertex.
Given any graph , we let refer to the graph with a dummy source added, where there is an edge of weight 0 from to for every and no edges into . Note that has a negative-weight cycle if and only if does and that .
For any integer , let denote the graph obtained by adding to all negative edge weights in , that is, for all and for . Note that so we can simply write .
For any graph and such that can reach all vertices in , define if ; otherwise, define
Let . When , let be a shortest -path on such that(1)
We omit when is the dummy source in defined in Definition 1; that is, , , and Further, the graph is omitted if the context is clear.
2.1 Price Functions and Equivalence
Our algorithm heavily relies on price functions, originally introduced by Johnson21
Consider a graph and let be any function: , where is the set of integers. Then, we define to be the weight function and we define . We will refer to as a price function on . Note that .
We say that two graphs and are equivalent if (1) any shortest path in is also a shortest path in and vice-versa and (2) contains a negative-weight cycle if and only if does.
Consider any graph and price function . For any pair we have , and for any cycle we have . As a result, and are equivalent. Finally, if , and for some positive , then and are equivalent.
The overall goal of our algorithm will be to compute a price function such that all edge weights in are non-negative (assuming no negative-weight cycle); we can then run Dijkstra on . The lemma below, originally used by Johnson, will be one of the tools we use.
Let be a directed graph with no negative-weight cycle and let be any vertex in that can reach all vertices in . Let for all . Then, all edge weights in are non-negative. (The lemma follows trivially from the fact that .)
3. The Framework
In this section we describe the input/output guarantees of all the subroutines used in our algorithm, as well as some of the algorithms themselves.
3.1 Key Subroutine: Low-Diameter Decomposition
Low-diameter decomposition in undirected graphs has been a key tool in graph algorithms dating back to the 80s, and there exist many variations of this core technique (for example, Awerbuch,2 Bartal,4 Linial and Saks,22 and Miller et al.23 for a small sample). More recent work presents a different formulation that is more appropriate to directed graphs,8 which is what we use in our paper.
In particular, one of our key subroutines is an algorithm that decomposes any directed graph with non-negative edge weights into strongly-connected components (SCCs) of small diameter. In particular, the algorithm computes a small set of edges such that all SCCs in the graph have small weak diameter. Although the lemma below only applies to non-negative weights, we will show that it is in fact extremely useful for our problem.
There is algorithm with the following guarantees:
INPUT: an -edge, -vertex graph with non-negative integer edge weight function and a positive integer .
OUTPUT: A set of edges with the following guarantees:
each SCC of has weak diameter at most ; that is, if are in the same SCC, then and .
For every , . These probabilities are not guaranteed to be independent.d
RUNNING TIME: The algorithm has running time .
This decomposition is new to this paper, but similar to other low-diameter decompositions used in both undirected and directed graphs, and especially to the algorithm Partition of Bernstein, Probst-Gutenberg, and Wulff-Nilsen.8 The main difference is that the algorithm of8 needed to work in a dynamic setting, and as a result their algorithm is too slow for our purposes.
Note that all the subroutines for low-diameter decomposition (including ours) only apply to graphs with non-negative edge weights. One of our main conceptual contributions is showing how to apply the subroutine to a problem with negative edge weights.
In this extended abstract, we use the above decomposition as a black box; details of the implementation can be found in the full version of the paper.7
3.2 Other Subroutines
There exists an algorithm called that takes as input a graph with non-negative edge weights and a vertex and outputs a shortest path tree from in . The running time is .
It is easy to see that if is a DAG (Directed Acyclic Graph), computing a price function such that has non-negative edge weights is straightforward: simply loop over the topological order and set so that all incoming edges have non-negative weight.
The lemma below generalizes this approach to graphs where only the “DAG part” has negative edges.
There exists an algorithm that takes as input a graph and a partition of vertices of such that
for every , the induced subgraph contains no negative-weight edges, and
when we contract every into a node, the resulting graph is a DAG (that is, contains no cycle).
The algorithm outputs a price function such that for all . The running time is .
The algorithm is extremely simple: it loops over the SCCs in topological order, and when it reaches it sets the same price for every that ensures there are no non-negative edges entering ; since all are the same, this does not affect edge-weights inside .
The next subroutine shows that computing shortest paths in a graph can be done efficiently as long as is small on average (see Definition 2 for ). Note that this subroutine is the reason we use the assumption that every vertex has constant out-degree (Assumption 1).
There exists an algorithm that takes as input a graph in which all vertices have constant out-degree and a source that can reach all vertices in . The algorithm outputs a price function such that for all and has running time (Definition 2); note that if contains a negative-weight cycle then so the algorithm will never terminate and hence not produce any output.
By Lemma 1, in order to compute the desired price function, it suffices to describe how computes for all , where is the input source to .
The algorithm is a straightforward combination of Dijkstra’s and Bellman-Ford’s algorithms. The algorithm maintains distance estimates for each vertex . It then proceeds in multiple iterations, where each iteration first runs a Dijkstra Phase that ensures that all non-negative edges are relaxed and then a Bellman-Ford Phase ensuring that all negative edges are relaxed. Consider a vertex and let be a shortest path from to in with edges of . It is easy to see that iterations suffice to ensure that . In each of these iterations, is extracted from and added to the priority queue of the Dijkstra Phase only times. Furthermore, after the iterations, will not be involved in any priority queue operations. Since the bottleneck in the running time is the queue updates, we get the desired time bound of .
3.3 The Interface of the Two Main Algorithms
No Negative-Weight Cycle Assumption. Although it is possible to prove Theorem 1 directly, the need to return the negative-weight cycle somewhat complicates the details. For this reason, we have written both algorithms below to only return correct distances when the input graph contains no negative-weight cycle; if the graph does have a negative-weight cycle, the algorithms offer no guarantees, and in fact might not even terminate. So for the sake of the intuition, we recommend the reader to focus on the case when the graph contains no negative-weight cycle. In the full version of the paper,7 we show that the weaker guarantees presented here can be transformed in a black-box manner to achieve the stronger guarantee of Theorem 1; the transformation incurs an extra factor in the runtime.
The Two Main Algorithms. Our two main algorithms are called and . The latter is responsible for actually returning the shorrtest path tree, and consists of a relatively simple outer shell. The main technical complexity lies in , which computes a price function that reduces the most negative edge weight by a factor of two. The procedure calls itself recursively, and the parameter tracks the layers of recursion.
There exists an algorithm that takes as input a graph and a source satisfying the properties of Assumption 1. If the algorithm terminates, it outputs a shortest path tree from . The running time guarantees are as follows:
If the graph contains a negative-weight cycle then the algorithm never terminates.
If the graph does not contain a negative-weight cycle then the algorithm has expected running time .
There exists the following algorithm .
INPUT REQUIREMENTS:
OUTPUT: If it terminates, the algorithm returns an integral price function such that for all
RUNNING TIME: If does not contain a negative-weight cycle, then the algorithm has expected runtime . Remark: If contains a negative-weight cycle, there is no guarantee on the runtime, and the algorithm might not even terminate; but if the algorithm does terminate, it always produces a correct output.
4. Algorithm
We start by describing the algorithm , as this contains our main conceptual contributions; the much simpler algorithm is described in the following section. Full pseudocode of is given in Algorithm 1. The algorithm mostly works with graph . For the analysis, the readers may want to familiarize themselves with, for example, , , and from Definitions 1 and 2. In particular, throughout this section, source always refers to a dummy source that has outgoing edges to every vertex in and has no incoming edges.
Note that since the input condition requires constant out-degree for every vertex. We thus use and interchangeably in this section. We briefly describe the algorithm and sketch the main ideas of the analysis in section 4.1; the full analysis follows in Section 4.2
4.1 Overview
The algorithm runs in phases, where in the last phase it calls for some price function (Line 10). Recall (Lemma 6) that if terminates, it returns price function such that all edge weights in are non-negative. Consequently, all edge weights in are non-negative for (since is a subgraph of ). We thus have for all as desired (because ). This already proves the output correctness of (Item 2 of Theorem 3). Thus it remains to bound the runtime when contains no negative-weight cycle Item 3). In the rest of this subsection we assume that contains no negative-weight cycle.
Bounding the runtime when is easy: The algorithm simply jumps to Phase 3 with (Line 1 in Algorithm 1). Since (the input requirement; Item 1b), the runtime of is .
For , we require some properties from Phases 0-2 in order to bound the runtime of Phase 3. In Phase 0, we partition vertices into strongly-connected components (SCCs)e such that each has weak diameter in . We do this by calling
where is obtained by rounding all negative weights in up to 0; we then let be the SCCs of . (We need since can not handle negative weights.f)
The algorithm now proceeds in three phases. In Phase 1 it computes a price function that makes the edges inside each SCC non-negative; in Phase 2 it computes such that the edges between SCCs in are also non-negative; finally, in Phase 3 it makes non-negative the edges in by calling .
(Phase 1) Our goal in Phase 1 is to compute such that for every edge in for all . To do this, we recursively call , where is a union of all the SCCs . The main reason that we can recursively call with parameter is because we can argue that, when does not contain a negative-weight cycle,
As a rough sketch, the above bound holds because if any shortest path from dummy source in some contains more than negative-weight edges, then it can be shown that ; this is the step where we crucially rely on the difference between and . Combining with the fact that has weak diameter at most implies that contains a negative-weight cycle.
(Phase 2) Now that all edges in are non-negative, we turn to the remaining edges in . Since these remaining edges (that is, those not in the SCCs) form a directed acyclic graph (DAG), we can simply call (Lemma 5) to get a price function such that all edges in are non-negative.
(Phase 3) By the time we reach this phase, the only negative edges remaining in are the ones in ; that is, . We call to eliminate these negative edges. We are now ready to show that the runtime of Phase 3, which is (Lemma 6), is in expectation. We do so by proving that for any ,
Details are in the next section, but a competitive reader might want to prove this equation via a series of inequalities: , and also, the guarantees of (Lemma 3) imply that after Phase 0,
Finally, observe that there are recursive calls, and the runtime of each call is dominated by the time of Phase 3. So, the total expected runtime is
4.2 Full Analysis
Theorem 3 follows from Theorems 4 and 5. We start with Theorem 4 which is quite trivial to prove.
either does not terminate or returns such that for all .
Consider when we call (Lemma 6) in Phase 3 for some integral price function Either this step does not terminate or returns an integral price function such that contains no negative-weight edges; that is, for all . Since , we have for all .
Theorem 4 implies that the output condition of (item 2 in Theorem 3) is always satisfied, regardless of whether contains a negative-weight cycle or not. It remains to show that if does not contain a negative-weight cycle, then has expected runtime of . It suffices to show the following.
If does not contain a negative-weight cycle, then the expected time complexity of Phase 3 is .
This suffices because, first of all, it is easy to see that Phase 0 requires time (by Lemma 3) and other phases (except the recursion on Line 7) requires time. Moreover, observe that if contains no negative-weight cycle, then the same holds for in the recursion call (Line 7 of Algorithm 1); thus, if contains no negative-weight cycle, then all recursive calls also get an input with no negative-weight cycle. So, by Theorem 5 the time to execute a single call in the recursion tree is in expectation. Since there are recursive calls, the total running time is by linearity of expectation.
Proof of Theorem 5. The rest of this subsection is devoted to proving Theorem 5. From now on, we consider any graph that does not contain a negative-weight cycle. (We often continue to state this assumption in lemma statements so that they are self-contained.)
Base case: Δ≤2. This means that for every vertex , (see the input requirement of in item 1b of Theorem 3). So, the runtime of Phase 3 is
We now consider when and show properties achieved in each phase. We will use these properties from earlier phases in analyzing the runtime of Phase 3.
Phase 0: Low-diameter Decomposition. It is straightforward that the SCCs have weak diameter at most (this property will be used in Phase 1):
For every and every ,
For every , we have
where the first inequality is because for every edge and the second inequality is by the output guarantee of (Lemma 3).
Another crucial property from the decomposition is this: Recall from Definition 2 that is the shortest -path in with negative-weight edges. We show below that in expectation contains only edges from . This will be used in Phase 3.
If , then for every ,
Consider any . The crux of the proof is the following bound on the weight of in :(2)
where we define for every . Recall the definition of of from Definition 1 and note that because there is an edge of weight 0 from to every . We thus have Equation (2) because:(3)
(The first inequality holds because for all ; the second inequality holds because ; the last inequality follows from the Definition of .)
Recall from the output guarantee of (Lemma 3) that , where in our case . This, the linearity of expectation, and (2) imply that
which is when .
Phase 1: Make edges inside the SCCs GB[Vi] non-negative. We argue that is called with an input that satisfies its input requirements (Theorem 3). The most important requirement is (Item 1b) which we prove below (other requirements are trivially satisfied). Recall that we set in Line 3.
If has no negative-weight cycle, then .
Consider any vertex . Let that is, is obtained by removing from a shortest -path in that contains negative weights in . Let be the first vertex in . Note three easy facts:
for all ,
, and
where (b) and (c) are because the edges from to and in have weight zero. Then,g(4)
Note that and are in the same SCC ;h thus, by Lemma 7:(5)
If contains no negative-weight cycle, then and thus by Equations (4) and (5). Since this holds for every , Lemma 9 follows.
Consequently, (Theorem 3) is guaranteed to output as follows.
If has no negative-weight cycle, then all edges in are non-negative for every .
Phase 2: Make all edges in GBErem non-negative. Now that all edges in are non-negative, we turn to the remaining edges in . Intuitively, since these remaining edges (that is, those not in the SCCs) form a directed acyclic graph (DAG), calling (Lemma 5) in Phase 2 produces the following result.
If has no negative-weight cycle, all weights in are non-negative.
Clearly, and satisfy the input conditions of Lemma 5, that is, (1) contains no negative-weight edges for every (this is due to Corollary 1), and (2) when we contract every into a node, the resulting graph is a DAG (since the are precisely the (maximal) SCCs of ).i Thus, returns such that contains no negative-weight edges.
Phase 3 runtime. Now we are ready to prove Theorem 5, that is, the runtime bound of in Phase 3 when contains no negative-weight cycle. We start by clarifying the nature of the graph . We start with the graph ; we then get by adding a dummy source with outgoing edges of weight 0 to every ; finally we get by applying price function to , where we define . The reason we apply at the end is to ensure that and are equivalent. Note that after we apply , the edges incident to can have non-zero weight (positive or negative); but can still reach every vertex, so we can still call with as the source.
Recall (Lemma 6 and definition 2) that the runtime of is
Fix any , observe that
where the inequality is because, for any price function , is a shortest -path in (because and are equivalent and is a shortest -path in by definition). By Lemma 10, all negative-weight edges in are in , that is, ; so,
where the “+1” term is because the edge incident to in can also be negative. By Lemma 8 and the fact that (input requirement Item 1b in Theorem 3),j
(6)(The last equality is by Lemma 8.) Thus, the expected runtime of is
5. Algorithm
In this section we present algorithm (Theorem 2), which always runs on the main input graph and source .
Description of Algorithm SPmain(Gin,sin). See Algorithm 2 for pseudocode. Recall that if contains a negative-weight cycle, then the algorithm is not supposed to terminate; for intuition, we recommend the reader focus on the case where contains no negative-weight cycle.
The algorithm first creates an equivalent graph by scaling up edge weights by (Line 1), and also rounds (Line 2), all to ensure that everything remains integral. It then repeatedly calls until we have a price function such that (See for loop in Line 4). The algorithm then defines a graph with (Line 7). We will argue that because we are dealing with the scaled graph , the additive is insignificant and does not affect the shortest path structure, so running Dijkstra on will return correct shortest paths in (Lines 8 and 9).
Correctness. We focus on the case where the algorithm terminates, and hence every line is executed. First we argue that weights in (Line 7) are non-negative.
If the algorithm terminates, then for all and we have that is integral and that for all . Note that this implies that for all , and so the graph has non-negative weights.
We prove the claim by induction on . For base case , the claim holds for because (see Assumption 1), so (see Lines 1 and 2).
Now assume by induction that the claim holds for . The call to in Line 5 satisfies the necessary input properties (See Theorem 3): property 1a holds by the induction hypotheses; property 1b holds because we have for any graph with no negative-weight cycle; property 1b holds because has constant out-degree, and the algorithm never changes the graph topology. Thus, by the output guarantee of we have that . The claim follows because as noted in Definition 3, .
If contains a negative-weight cycle then the algorithm does not terminate.
Say, for contradiction, that the algorithm terminates; then by Lemma 1 we have that . Now, let be any negative-weight cycle in . Since all weights in are multiples of (Line 1), we know that . But we also know that . So , which contradicts Lemma 1.
Now we show that the algorithm produces a correct output.
Say that contains no negative-weight cycle. Then, the algorithm terminates, and if is a shortest sv-path in (Line 7) then it is also a shortest sv-path in . Thus, the shortest path tree of computed in Line 9 is also a shortest path tree in .
The algorithm terminates because each call to terminates, because is equivalent to (Lemma 1) and so does not contain a negative-weight cycle. Now we show that(7)
which implies the claim because and are equivalent. We assume that because otherwise the claim is trivial. Observe that since all weights in are multiples of (Line 1), all shortest distances are also multiples of , so for any two -paths and , is either 0 or . It is easy to check that by Lemma 1, we also have that(8)
Moreover, by definition of we have(9)
Now, we prove (7). Assume for contradiction that there was a shorter path in . Then,(10)
So, contradicting being shortest in .
Running Time Analysis. By Corollary 2, if does not contain a negative-weight cycle then the algorithm does not terminate, as desired. We now focus on the case where does not contain a negative-weight cycle. The running time of the algorithm is dominated by the calls to . Note that all the input graphs are equivalent to , so they do not contain a negative-weight cycle. By Theorem 3, the expected runtime of each call to is . So, the expected runtime of is .
Acknowledgment We thank Sepehr Assadi, Joakim Blikstad, Thatchaphol Saranurak, and Satish Rao for their comments on the early draft of the paper and the discussions. We thank Mohsen Ghaffari, Merav Parter, Satish Rao, and Goran Zuzic for pointing out some literature on low-diameter decomposition. A discussion with Mohsen Ghaffari led to some simplifications of our low-diameter decomposition algorithm. We also thank Vikrant Ashvinkumar, Nairen Cao, Christoph Grunau, and Yonggang Jiang for pointing out a technical error in an earlier version of the paper.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment