Research Highlights
Theory

Negative-Weight Single-Source Shortest Paths in Near-Linear Time

We present a randomized algorithm that essentially resolves the classic negative-weight single-source shortest paths problem.

Posted
aerialist on a tightrope
Read the related Technical Perspective

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(mn 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 m-edge n-vertex directed weighted graph G=(V,E,w) with integral edge weight w(e) for every edge eE and a source vertex sV, the goal is to compute a shortest path from s.

Two textbook algorithms for SSSP are Bellman-Ford and Dijkstra’s algorithm. Dijkstra’s algorithm is near-linear time (O(m+nlogn) 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 s in G; in particular, the algorithm either returns a shortest path tree from s or returns a cycle reachable from s whose total weight is negative. Unfortunately, the runtime of Bellman-Ford is O(mn).

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 O(mnlogW), where W2 is the minimum integer such that w(e)W for all eE. 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 (O~((m+n1.5)logW) time) on moderately dense graphs10 and m4/3+o(1)logW runtime on sparse graphs.3,a This state of the art motivates two natural questions:

  1. Can we get near-linear runtime for all graphs?

  2. 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 O(mnlog(W)) 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.

Theorem 1.

There exists a randomized (Las Vegas) algorithm that takes O(mlog8(n)log(W)) time with high probability (and in expectation) for an m-edge input graph Gin and source sin. It either returns a shortest path tree from sin 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 O(m1+o(1)log2U) for minimum-cost flow.b This directly implies a runtime of m1+o(1)log(W) 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 O(mlog2(n)log(nW)loglogn). 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 G=(V,E,w), define V(G)=V,E(G)=E, and

E n e g ( G ) : = { e E | w ( e ) < 0 } .

Define WG:=max{2,mineE{w(e)}}; that is, WG is the most negative edge weight in the graph.c Given any set of edges SE we define w(S)=eSw(e). We say that a cycle C in G is a negative-weight cycle if w(C)<0. We define distG(u,v) to be the shortest distance from u to v in graph G; if there is a negative-weight cycle on some uv-path then we define distG(u,v)=.

Consider graph G=(V,E,w) and consider subsets VV and EE. We define G[V] to be the subgraph of G induced by V. We slightly abuse notation and denote a subgraph of G as H=(V,E,w) where the weight function w is restricted to edges in H. We define GV=G[VV] and GE=(V,EE,w); that is, they are graphs where we remove vertices and edges in V and E respectively. We sometimes write Gv and Ee instead of G{v} and G{e}, respectively, for any vV and eE. We say that a subgraph H of G has weak diameter D if for any u,vV(H) we have that distG(u,v)D. We always let Gin and sin refer to the main input graph/source of Theorem 1.

Assumption 1 (Properties of input graph Gin).

We assume throughout the paper that the main input graph Gin=(V,E,win) satisfies the following properties:

  1. win(e)1 for all eE (thus, WGin=2).

  2. Every vertex in Gin 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 sin, but instead to a dummy source that has edges of weight 0 to every vertex.

Definition 1.

Given any graph G=(V,E,w), we let Gs=(V{s},E{(s,v)}vV,ws) refer to the graph G with a dummy source s added, where there is an edge of weight 0 from s to v for every vV and no edges into s. Note that Gs has a negative-weight cycle if and only if G does and that distGs(s,v)=minuVdistG(u,v).

For any integer B, let GB=(V,E,wB) denote the graph obtained by adding B to all negative edge weights in G, that is, wB(e)=w(e)+B for all eEneg(G) and wB(e)=w(e) for eEEneg(G). Note that (GB)s=(Gs)B so we can simply write GsB=(V{s},E{(s,v)}vV,wsB).

Definition 2.

For any graph G=(V,E,w) and sV such that s can reach all vertices in V, define ηG(v):= if distG(s,v)=; otherwise, defineηG(v):=min{|Eneg(G)P|:Pisashortestsv-pathinG}

Let η(G;s)=maxvVηG(v;s). When distG(s,v), let PG(v;s) be a shortest sv-path on G such that|Eneg(G)PG(v)|=ηG(v).

We omit s when s is the dummy source in Gs defined in Definition 1; that is, ηG(v)=ηGs(v;s), η(G)=η(Gs;s), and PG(v)=PGs(v;s). Further, the graph G is omitted if the context is clear.

2.1 Price Functions and Equivalence

Our algorithm heavily relies on price functions, originally introduced by Johnson21

Definition 3.

Consider a graph G=(V,E,w) and let ϕ be any function: V, where is the set of integers. Then, we define wϕ to be the weight function wϕ(u,v)=w(u,v)+ϕ(u)ϕ(v) and we define Gϕ=(V,E,wϕ). We will refer to ϕ as a price function on V. Note that (Gϕ)ψ=Gϕ+ψ.

Definition 4.

We say that two graphs G=(V,E,w) and G=(V,E,w) are equivalent if (1) any shortest path in G is also a shortest path in G and vice-versa and (2) G contains a negative-weight cycle if and only if G does.

Lemma 1.21

Consider any graph G=(V,E,w) and price function ϕ. For any pair u,vV we have distGϕ(u,v)=distG(u,v)+ϕ(u)ϕ(v), and for any cycle C we have w(C)=wϕ(C). As a result, G and Gϕ are equivalent. Finally, if G=(V,E,w), G=(V,E,w) and w=c·w(e) for some positive c, then G and G are equivalent.

The overall goal of our algorithm will be to compute a price function ϕ such that all edge weights in Gϕ are non-negative (assuming no negative-weight cycle); we can then run Dijkstra on Gϕ. The lemma below, originally used by Johnson, will be one of the tools we use.

Lemma 2.21

Let G=(V,E) be a directed graph with no negative-weight cycle and let s be any vertex in G that can reach all vertices in V. Let ϕ(v)=distG(s,v) for all vV. Then, all edge weights in Gϕ are non-negative. (The lemma follows trivially from the fact that dist(s,v)dist(s,u)+w(u,v).)

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 Erem such that all SCCs in the graph GErem 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.

Lemma 3.

There is algorithm LowDiamDecomposition(G,D) with the following guarantees:

  • INPUT: an m-edge, n-vertex graph G=(V,E,w) with non-negative integer edge weight function w and a positive integer D.

  • OUTPUT: A set of edges Erem with the following guarantees:

    • each SCC of GErem has weak diameter at most D; that is, if u,v are in the same SCC, then distG(u,v)D and distG(v,u)D.

    • For every eE, Pr[eErem]=Ow(e)·log2nD+n10. These probabilities are not guaranteed to be independent.d

  • RUNNING TIME: The algorithm has running time O(mlog2n+nlog3n).

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

Lemma 4 (Dijkstra).

There exists an algorithm called Dijkstra(G,s) that takes as input a graph G with non-negative edge weights and a vertex sV and outputs a shortest path tree from s in G. The running time is O(m+nlog(n)).

It is easy to see that if G is a DAG (Directed Acyclic Graph), computing a price function ϕ such that Gϕ has non-negative edge weights is straightforward: simply loop over the topological order v1,...,vn and set ϕ(vi) 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.

Lemma 5 (FixDAGEdges).

There exists an algorithm FixDAGEdges(G,P) that takes as input a graph G and a partition P:={V1,V2,} of vertices of G such that

  1. for every i, the induced subgraph G[Vi] contains no negative-weight edges, and

  2. when we contract every Vi into a node, the resulting graph is a DAG (that is, contains no cycle).

The algorithm outputs a price function ϕ:V such that wϕ(u,v)0 for all (u,v)E. The running time is O(m+n).

Proof sketch.

The algorithm is extremely simple: it loops over the SCCs Vi in topological order, and when it reaches Vi it sets the same price ϕ(v) for every vVi that ensures there are no non-negative edges entering Vi; since all ϕ(v) are the same, this does not affect edge-weights inside Vi.

The next subroutine shows that computing shortest paths in a graph G can be done efficiently as long as η(v) is small on average (see Definition 2 for η(v)). Note that this subroutine is the reason we use the assumption that every vertex has constant out-degree (Assumption 1).

Lemma 6 ((ElimNeg)).

There exists an algorithm ElimNeg(G,s) that takes as input a graph G=(V,E,w) in which all vertices vs have constant out-degree and a source sV that can reach all vertices in V. The algorithm outputs a price function ϕ such that wϕ(e)0 for all eE and has running time O(log(n)·(n+vVηG(v;s))) (Definition 2); note that if G contains a negative-weight cycle then vVηG(v;s)= so the algorithm will never terminate and hence not produce any output.

Proof Sketch.

By Lemma 1, in order to compute the desired price function, it suffices to describe how ElimNeg(G) computes distG(s,v) for all vV, where s is the input source to ElimNeg(G,s).

The algorithm is a straightforward combination of Dijkstra’s and Bellman-Ford’s algorithms. The algorithm maintains distance estimates d(v) for each vertex v. 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 v and let P be a shortest path from s to v in G with ηG(v;s) edges of Eneg(G). It is easy to see that ηG(v;s)+1 iterations suffice to ensure that d(v)=distG(s,v). In each of these iterations, v is extracted from and added to the priority queue of the Dijkstra Phase only O(1) times. Furthermore, after the ηG(v;s)+1 iterations, v 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 O(log(n)·vV(ηG(v;s)+1))=O(log(n)·(n+vVηG(v;s))).

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 G 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 O(log2(n)) factor in the runtime.

The Two Main Algorithms.  Our two main algorithms are called ScaleDown and SPmain. 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 ScaleDown, which computes a price function that reduces the most negative edge weight by a factor of two. The procedure ScaleDown calls itself recursively, and the parameter δ tracks the layers of recursion.

Theorem 2 (SPmain).

There exists an algorithm SPmain(Gin,sin) that takes as input a graph Gin and a source sin satisfying the properties of Assumption 1. If the algorithm terminates, it outputs a shortest path tree T from sin. The running time guarantees are as follows:

  • If the graph Gin contains a negative-weight cycle then the algorithm never terminates.

  • If the graph Gin does not contain a negative-weight cycle then the algorithm has expected running time Tspmain=O(mlog5(n)).

Theorem 3 (ScaleDown).

There exists the following algorithm ScaleDown(G=(V,E,w),Δ,B).

  1. INPUT REQUIREMENTS:

    1. B is positive integer, w is integral, and w(e)2B for all eE

    2. If the graph G does not contain a negative-weight cycle then the input must satisfy η(GB)Δ; that is, for every vV there is a shortest sv-path in GsB with at most Δ negative edges (Definitions 1 and 2)

    3. All vertices in G have constant out-degree

  2. OUTPUT: If it terminates, the algorithm returns an integral price function ϕ such that wϕ(e)B for all eE

  3. RUNNING TIME: If G does not contain a negative-weight cycle, then the algorithm has expected runtime Omlog3(n)log(Δ). Remark: If G 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 ScaleDown

Algorithm 1.  Algorithm for ScaleDown(G=(V,E,w),Δ,B)

We start by describing the algorithm ScaleDown, as this contains our main conceptual contributions; the much simpler algorithm SPmain is described in the following section. Full pseudocode of ScaleDown is given in Algorithm 1. The algorithm mostly works with graph GB=(V,E,wB). For the analysis, the readers may want to familiarize themselves with, for example, GsB, wsB, PGB(v) and η(GB) from Definitions 1 and 2. In particular, throughout this section, source salways refers to a dummy source that has outgoing edges to every vertex in V and has no incoming edges.

Note that m=Θ(n) since the input condition requires constant out-degree for every vertex. We thus use m and n interchangeably in this section. We briefly describe the ScaleDown 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 ElimNeg((GsB)ϕ2,s) for some price function ϕ2 (Line 10). Recall (Lemma 6) that if ElimNeg terminates, it returns price function ψ such that all edge weights in (GsB)ϕ2+ψ are non-negative. Consequently, all edge weights in Gϕ3B are non-negative for ϕ3=ϕ2+ψ (since Gϕ2B is a subgraph of (GsB)ϕ2). We thus have wϕ3(e)B for all eE as desired (because wB(e)w(e)+B). This already proves the output correctness of ScaleDown (Item 2 of Theorem 3). Thus it remains to bound the runtime when G contains no negative-weight cycle Item 3). In the rest of this subsection we assume that G contains no negative-weight cycle.

Bounding the runtime when Δ2 is easy: The algorithm simply jumps to Phase 3 with ϕ2=0 (Line 1 in Algorithm 1). Since η(GB)Δ2 (the input requirement; Item 1b), the runtime of ElimNeg((GsB)ϕ2,s) is O((m+vVηGB(v))logm)=O(mΔlogm)=O(mlogm).

For Δ>2, 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 V1,V2, such that each Vi has weak diameter dB=BΔ/2 in G. We do this by calling

E r e m LowDiamDecomposition ( G 0 B , d B ) ,

where G0B is obtained by rounding all negative weights in GB up to 0; we then let V1,V2, be the SCCs of GBErem. (We need G0B since LowDiamDecomposition can not handle negative weights.f)

The algorithm now proceeds in three phases. In Phase 1 it computes a price function ϕ1 that makes the edges inside each SCC Vi non-negative; in Phase 2 it computes ϕ2 such that the edges between SCCs in GBErem are also non-negative; finally, in Phase 3 it makes non-negative the edges in Erem by calling ElimNeg.

(Phase 1) Our goal in Phase 1 is to compute ϕ1 such that wϕ1B(e)0 for every edge e in GB[Vi] for all i. To do this, we recursively call ScaleDown(H,Δ/2,B), where H is a union of all the SCCs G[Vi]. The main reason that we can recursively call ScaleDown with parameter Δ/2 is because we can argue that, when G does not contain a negative-weight cycle,

η ( H B ) d = Δ / 2 .

As a rough sketch, the above bound holds because if any shortest path P from dummy source s in some (GB[Vi])s contains more than d negative-weight edges, then it can be shown that w(P)<dB; this is the step where we crucially rely on the difference between wB(P) and w(P). Combining w(P)<dB with the fact that GB[Vi] has weak diameter at most dB implies that G contains a negative-weight cycle.

(Phase 2) Now that all edges in Gϕ1B[Vi] are non-negative, we turn to the remaining edges in GBErem. Since these remaining edges (that is, those not in the SCCs) form a directed acyclic graph (DAG), we can simply call FixDAGEdges(Gϕ1BErem,{V1,V2,}) (Lemma 5) to get a price function ψ such that all edges in (Gϕ1BErem)ψ=Gϕ2BErem are non-negative.

(Phase 3) By the time we reach this phase, the only negative edges remaining in Gϕ2B are the ones in Erem; that is, Eneg(Gϕ2B)Erem. We call ElimNeg((GsB)ϕ2,s) to eliminate these negative edges. We are now ready to show that the runtime of Phase 3, which is O((m+vVη(GsB)ϕ2(v;s))logm) (Lemma 6), is O(mlog3m) in expectation. We do so by proving that for any vV,

E η ( G s B ) ϕ 2 ( v ; s ) = O ( log 2 m ) .

Details are in the next section, but a competitive reader might want to prove this equation via a series of inequalities: η(GsB)ϕ2(v)|PGB(v)Eneg(Gϕ2B)|+1|PGB(v)Erem|+1, and also, the guarantees of LowDiamDecomposition (Lemma 3) imply that after Phase 0, E|PGB(v)Erem|=O(log2m).

Finally, observe that there are O(logΔ) recursive calls, and the runtime of each call is dominated by the O(mlog3m) time of Phase 3. So, the total expected runtime is O(mlog3(m)logΔ)

4.2 Full Analysis

Theorem 3 follows from Theorems 4 and 5. We start with Theorem 4 which is quite trivial to prove.

Theorem 4.

ScaleDown(G=(V,E,w),Δ,B) either does not terminate or returns ϕ=ϕ3 such that wϕ(e)B for all eE.

Proof.

Consider when we call ElimNeg((GsB)ϕ2,s)(Lemma 6) in Phase 3 for some integral price function ϕ2. Either this step does not terminate or returns an integral price function ψ such that (Gϕ2B)ψ=Gϕ2+ψB=Gϕ3B contains no negative-weight edges; that is, wϕ3B(e)0 for all eE. Since wB(e)w(e)+B, we have wϕ3(e)wϕ3B(e)BB for all eE.

Theorem 4 implies that the output condition of ScaleDown (item 2 in Theorem 3) is always satisfied, regardless of whether G contains a negative-weight cycle or not. It remains to show that if G does not contain a negative-weight cycle, then ScaleDown(G=(V,E,w),Δ,B) has expected runtime of O(mlog3(m)log(Δ)). It suffices to show the following.

Theorem 5.

If G does not contain a negative-weight cycle, then the expected time complexity of Phase 3 is O(mlog3m).

This suffices because, first of all, it is easy to see that Phase 0 requires O(mlog3(m)) time (by Lemma 3) and other phases (except the recursion on Line 7) requires O(m+n) time. Moreover, observe that if G contains no negative-weight cycle, then the same holds for H in the recursion call ScaleDown(H,Δ/2,B) (Line 7 of Algorithm 1); thus, if G 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 O(mlog3m) in expectation. Since there are O(logΔ) recursive calls, the total running time is O(mlog3(m)log(Δ)) 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 G 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 v, ηGB(v)η(GB)Δ2 (see the input requirement of ScaleDown in item 1b of Theorem 3). So, the runtime of Phase 3 is

O m + v V η G B ( v ) log m = O m Δ log m = O m log m .

We now consider when Δ>2 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 G[Vi] have weak diameter at most dB (this property will be used in Phase 1):

Lemma 7.

For every i and every u,vVi, distG(u,v)dB.

Proof.

For every u,vVi, we have

dist G ( u , v ) dist G 0 B ( u , v ) d B

where the first inequality is because w(e)w0B(e) for every edge eE and the second inequality is by the output guarantee of LowDiamDecomposition (Lemma 3).

Another crucial property from the decomposition is this: Recall from Definition 2 that PGB(v) is the shortest sv-path in GsB with ηGB(v) negative-weight edges. We show below that in expectation PGB(v) contains only O(log2n) edges from Erem. This will be used in Phase 3.

Lemma 8.

If η(GB)Δ, then for every vV,EPGB(v)Erem=O(log2m).

Proof.

Consider any vV. The crux of the proof is the following bound on the weight of PGB(v) in G0B:w0B(PGB(v))ηGB(v)·B

where we define w0B(s,u)=0 for every uV. Recall the definition of of wsB from Definition 1 and note that wsB(PGB(v))0 because there is an edge of weight 0 from s to every vV. We thus have Equation (2) because:w0B(PGB(v))wsB(PGB(v))+|PGB(v)Eneg(GB)|·B|PGB(v)Eneg(GB)|·B=ηGB(v)·B

(The first inequality holds because wB(e)B for all eE; the second inequality holds because wsB(PGB(v))0; the last inequality follows from the Definition of PGB(v).)

Recall from the output guarantee of LowDiamDecomposition (Lemma 3) that Pr[eErem]=O(w0B(e)·(logn)2/D+n10), where in our case D=dB=BΔ/2. This, the linearity of expectation, and (2) imply thatE[PGB(v)Erem]=Ow0B(PGB(v))·(logn)2BΔ/2+|(PGB(v))|·n10=(2)O2ηGB(v)·(logn)2Δ+n9

which is O(log2n) when η(GB)Δ.

Phase 1: Make edges inside the SCCs GB[Vi] non-negative.  We argue that ScaleDown(H,Δ/2,B) is called with an input that satisfies its input requirements (Theorem 3). The most important requirement is η(HB)Δ/2 (Item 1b) which we prove below (other requirements are trivially satisfied). Recall that we set d:=Δ/2 in Line 3.

Lemma 9.

If G has no negative-weight cycle, then η(HB)d=Δ/2.

Proof.

Consider any vertex vV. Let P:=PHB(v)s; that is, P is obtained by removing s from a shortest sv-path in HsB that contains ηHB(v) negative weights in HsB. Let u be the first vertex in P. Note three easy facts:

  1. wHB(e)=wH(e)+B for all eEneg(HB),

  2. |Eneg(HB)P|=|Eneg(HB)PHB(v)|=ηHB(v), and

  3. wHB(P)=wHsB(PHB(v))wHsB(s,v)=0,

where (b) and (c) are because the edges from s to u and v in HsB have weight zero. Then,gdistG(u,v)wH(P)(a)wHB(P)|Eneg(HB)P|·B=(b)wHB(P)ηHB(v)·B(c)ηHB(v)·B.

Note that u and v are in the same SCC Vi;h thus, by Lemma 7:distG(v,u)dB.

If G contains no negative-weight cycle, then distG(u,v)+distG(v,u)0 and thus ηHB(v)dB·(1/B)=d by Equations (4) and (5). Since this holds for every vV, Lemma 9 follows.

Consequently, ScaleDown (Theorem 3) is guaranteed to output ϕ1 as follows.

Corollary 1.

If G has no negative-weight cycle, then all edges in Gϕ1B[Vi] are non-negative for every i.

Phase 2: Make all edges in GBErem non-negative.  Now that all edges in Gϕ1B[Vi] are non-negative, we turn to the remaining edges in GBErem. Intuitively, since these remaining edges (that is, those not in the SCCs) form a directed acyclic graph (DAG), calling FixDAGEdges(Gϕ1BErem,{V1,V2,}) (Lemma 5) in Phase 2 produces the following result.

Lemma 10.

If G has no negative-weight cycle, all weights in Gϕ2BErem are non-negative.

Proof.

Clearly, Gϕ1BErem and {V1,V2,} satisfy the input conditions of Lemma 5, that is, (1) (GBErem)ϕ1[Vi] contains no negative-weight edges for every i (this is due to Corollary 1), and (2) when we contract every Vi into a node, the resulting graph is a DAG (since the Vi are precisely the (maximal) SCCs of Gϕ1BErem).i Thus, FixDAGEdges((GBErem)ϕ1,{V1,V2,}) returns ψ such that (Gϕ1BErem)ψ=Gϕ2BErem contains no negative-weight edges.

Phase 3 runtime.  Now we are ready to prove Theorem 5, that is, the runtime bound of ElimNeg((GsB)ϕ2,s) in Phase 3 when G contains no negative-weight cycle. We start by clarifying the nature of the graph (GsB)ϕ2. We start with the graph GB; we then get GsB by adding a dummy source with outgoing edges of weight 0 to every vV; finally we get (GsB)ϕ2 by applying price function ϕ2 to GsB, where we define ϕ2(s)=0. The reason we apply ϕ2 at the end is to ensure that GsB and (GsB)ϕ2 are equivalent. Note that after we apply ϕ2, the edges incident to s can have non-zero weight (positive or negative); but s can still reach every vertex, so we can still call ElimNeg with s as the source.

Recall (Lemma 6 and definition 2) that the runtime of ElimNeg((GsB)ϕ2,s) is

O m + v V η ( G s B ) ϕ 2 ( v ; s ) log m

Fix any vV, observe that

η ( G s B ) ϕ 2 ( v ; s ) = min { | P E n e g ( ( G s B ) ϕ 2 ) | : P is a shortest s v -path in ( G s B ) ϕ 2 } | P G B ( v ) E n e g ( ( G s B ) ϕ 2 ) |

where the inequality is because, for any price function ϕ2, PGB(v) is a shortest sv-path in (GsB)ϕ2 (because (GsB)ϕ2 and GsB are equivalent and PGB(v) is a shortest sv-path in GsB by definition). By Lemma 10, all negative-weight edges in Gϕ2B are in Erem, that is, Eneg(Gϕ2B)Erem; so,

η ( G s B ) ϕ 2 ( v ; s ) | P G B ( v ) E r e m | + 1

where the “+1” term is because the edge incident to s in PGB(v) can also be negative. By Lemma 8 and the fact that η(GB)Δ (input requirement Item 1b in Theorem 3),j

E η ( G s B ) ϕ 2 ( v ; s ) E P G B ( v ) E r e m + 1 = O ( log 2 m ) .

(The last equality is by Lemma 8.) Thus, the expected runtime of ElimNeg((GsB)ϕ2,s) is

O m + E v V η ( G s B ) ϕ 2 ( v ; s ) log m = O m log 3 m .

5. Algorithm SPmain

In this section we present algorithm SPmain(Gin,sin) (Theorem 2), which always runs on the main input graph Gin and source sin.

Description of Algorithm SPmain(Gin,sin).  See Algorithm 2 for pseudocode. Recall that if Gin contains a negative-weight cycle, then the algorithm is not supposed to terminate; for intuition, we recommend the reader focus on the case where Gin contains no negative-weight cycle.

The algorithm first creates an equivalent graph G¯ by scaling up edge weights by 2n (Line 1), and also rounds B (Line 2), all to ensure that everything remains integral. It then repeatedly calls ScaleDown until we have a price function ϕt such that wϕt(e)1 (See for loop in Line 4). The algorithm then defines a graph G*=(V,E,w*) with w*(e)=wϕt(e)+1 (Line 7). We will argue that because we are dealing with the scaled graph G¯, the additive +1 is insignificant and does not affect the shortest path structure, so running Dijkstra on G* will return correct shortest paths in G (Lines 8 and 9).

Algorithm 2.  SPmain ( G i n = ( V , E , w i n ) , s i n )

Correctness.  We focus on the case where the algorithm terminates, and hence every line is executed. First we argue that weights in G* (Line 7) are non-negative.

Claim 1.

If the algorithm terminates, then for all eE and i[0,t:=log2(B)] we have that w¯i is integral and that w¯i(e)B/2i for all eE. Note that this implies that w¯t(e)1 for all eE, and so the graph G* has non-negative weights.

Proof.

We prove the claim by induction on i. For base case i=0, the claim holds for G¯ϕ0=G¯ because win(e)1 (see Assumption 1), so w¯(e)2nB (see Lines 1 and 2).

Now assume by induction that the claim holds for G¯ϕi1. The call to ScaleDown(G¯ϕi1,Δ:=n,B/2i) in Line 5 satisfies the necessary input properties (See Theorem 3): property 1a holds by the induction hypotheses; property 1b holds because we have ηG(v)n for any graph G with no negative-weight cycle; property 1b holds because Gin has constant out-degree, and the algorithm never changes the graph topology. Thus, by the output guarantee of ScaleDown we have that (w¯ϕi1)ψi(e)(B/2i1)/2=B/2i. The claim follows because as noted in Definition 3, (w¯ϕi1)ψi=w¯ϕi1+ψi=w¯ϕi.

Corollary 2.

If Gin contains a negative-weight cycle then the algorithm does not terminate.

Proof.

Say, for contradiction, that the algorithm terminates; then by Lemma 1 we have that w¯ϕt(e)1. Now, let C be any negative-weight cycle in Gin. Since all weights in G¯ are multiples of 2n (Line 1), we know that w¯(C)2n. But we also know that w¯ϕt(C)|C|n. So w¯(C)w¯ϕt(C), which contradicts Lemma 1.

Now we show that the algorithm produces a correct output.

Claim 2.

Say that Gin contains no negative-weight cycle. Then, the algorithm terminates, and if P is a shortest sv-path in G* (Line 7) then it is also a shortest sv-path in Gin. Thus, the shortest path tree T of G* computed in Line 9 is also a shortest path tree in Gin.

Proof.

The algorithm terminates because each call to ScaleDown(G¯ϕi1,Δ:=n,B/2i) terminates, because G¯ϕi1 is equivalent to Gin (Lemma 1) and so does not contain a negative-weight cycle. Now we show thatPisalsoashortestpathinG¯ϕt

which implies the claim because G¯ϕt and Gin are equivalent. We assume that sv because otherwise the claim is trivial. Observe that since all weights in G¯ are multiples of 2n (Line 1), all shortest distances are also multiples of 2n, so for any two sv-paths Psv and Psv, |w¯(Psv)w¯(Psv)| is either 0 or >n. It is easy to check that by Lemma 1, we also have that|w¯ϕt(Psv)w¯ϕt(Psv)|iseither0or>n.

Moreover, by definition of G* we havew¯ϕt(Psv)<w*(Psv)=w¯ϕt(Psv)+|Psv|<w¯ϕt(Psv)+n.

Now, we prove (7). Assume for contradiction that there was a shorter path P in G¯ϕt. Then,w¯ϕt(P)w¯ϕt(P)>()n.

So, w*(P)<()w¯ϕt(P)+n<()w¯ϕt(P)<()w*(P), contradicting P being shortest in G*.

Running Time Analysis.  By Corollary 2, if Gin does not contain a negative-weight cycle then the algorithm does not terminate, as desired. We now focus on the case where Gin does not contain a negative-weight cycle. The running time of the algorithm is dominated by the log(B)=O(log(n)) calls to ScaleDown(G¯ϕi1,Δ:=n,B/2i). Note that all the input graphs G¯ϕi1 are equivalent to Gin, so they do not contain a negative-weight cycle. By Theorem 3, the expected runtime of each call to ScaleDown is O(mlog3(n)log(Δ))=O(mlog4(n)). So, the expected runtime of SPmain is O(mlog5(n)).

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.

    References

    • 1. Ashvinkumar, V. et al. Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights, 2023.
    • 2. Awerbuch, B. Complexity of network synchronization. J. ACM 32, 4 (1985), 804823. Announced at STOC’84.
    • 3. Axiotis, K., Madry, A., and Vladu, A. Circulation control for faster minimum cost flow in unit-capacity graphs. In FOCS. IEEE, 2020, 93104.
    • 4. Bartal, Y. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symp. On Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996. IEEE Computer Society, 1996, 184193.
    • 5. Bellman, R. On a routing problem. Quarterly of Applied Mathematics 16, 1, (1958), 8790.
    • 6. Bernstein, A. et al.  Fully-dynamic graph sparsifiers against an adaptive adversary. CoRR, abs/2004.08432, 2020.
    • 7. Bernstein, A., Nanongkai, D., and Wulff-Nilsen, C. Negative-weight single-source shortest paths in almost-linear time. CoRR, abs/2203.03456, 2022.
    • 8. Bernstein, A., Probst Gutenberg, M., and Wulff-Nilsen, C. Near-optimal decremental SSSP in dense weighted digraphs. 61st IEEE Annual Symp. on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. S.Irani (Ed.). IEEE, 2020, 11121122.
    • 9. Brand, J.v.d. et al. Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances. In STOC. ACM, 2021, 859869.
    • 10. Brand, J.v.d. et al. Bipartite matching in nearly-linear time on moderately dense graphs. In FOCS. IEEE, 2020, 919930.
    • 11. Brand, J.v.d., Lee, Y.T., Sidford, A., and Song, Z. Solving tall dense linear programs in nearly linear time. In STOC, 2020.
    • 12. Bringmann, K., Cassis, A., and Fischer, N. Negative-weight single-source shortest paths in near-linear time: Now faster! CoRR, abs/2304.05279, 2023.
    • 13. Chen, L. et al. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time, Mar. 2022.
    • 14. Chuzhoy, J. et al. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In FOCS, 2020.
    • 15. Cohen, M.B., Madry, A., Sankowski, P., and Vladu, A. Negative-weight shortest paths and unit capacity minimum cost flow in Õ(m10/7 log W) time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symp. on Discrete Algorithms (SODA). SIAM, 2017, 752771.
    • 16. Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.
    • 17. Ford, R. Paper P-923. The RAND Corperation, Santa Moncia, California, 1956.
    • 18. Gabow, H.N. Scaling algorithms for network problems. J. Comput. Syst. Sci. 312 (1985), 148168. announced at FOCS’83.
    • 19. Gabow, H.N. and Tarjan, R.E. Faster scaling algorithms for network problems. SIAM J. Comput. 185 (1989), 10131036.
    • 20. Goldberg, A.V. Scaling algorithms for the shortest paths problem. SIAM J. Comput. 243 (1995), 494504. Announced at SODA’93.
    • 21. Johnson, D.B. Efficient algorithms for shortest paths in sparse networks. J. ACM 241 (1977), 113.
    • 22. Linial, N. and Saks, M.E. Low diameter graph decompositions. Comb 13 4 (1993), 441454.
    • 23. Miller, G.L., Peng, R., and Xu, S.C. Parallel graph decompositions using random shifts. In 25th ACM Symp. on Parallelism in Algorithms and Architectures, SPAA ’13, Montreal, QC, Canada, July 23 - 25, 2013. G. E.Blelloch and B.Vöocking (Eds.). ACM, 2013, 196203.
    • 24. Nanongkai, D., Saranurak, T., and Wulff-Nilsen, C. Dynamic minimum spanning forest with subpolynomial worst-case update time. In FOCS. IEEE Computer Society, 2017, 950961.
    • 25. Saranurak, T. and Wang, D. Expander decomposition and pruning: Faster, stronger, and simpler. In SODA. SIAM, 2019, 26162635.
    • O~-notation hides polylogarithmic factors.
    • The runtime is for when vertex demands, edge costs, and upper/lower edge capacities are all integral and bounded by U in absolute value.
    • We set WG2 so that we can write log(WG) in our runtime
    • The 10 in the exponent suffices for our application but can be replaced by an arbitrarily large constant.
    • Recall that a SCC is a maximal set CV such that for every u,vV, there are paths from u to v and from v to u. See, for example, Chapter 22.5 in Cormen et al.16
    • One can also use G0 instead of G0B. We choose G0B since some proofs become slightly simpler.
    • The “(a)” part in (4) is not equality because there can be an edge in Eneg(H)P that is not in Eneg(HB)P.
    • in fact all vertices in P are in the same SCC Vi, because we define H=iG[Vi].
    • See, for example, Lemma 22.13 in Cormen et al.16
    • The expectation in (6) is over the random outcomes of the low-diameter decomposition in Phase 0 and the recursion in Phase 1. Note that both η(GsB)ϕ2(v;s) and |PGB(v)Erem| are random variables. Since we always have η(GsB)ϕ2(v;s)|PGB(v)Erem|+1, we also have Eη(GsB)ϕ2(v;s)EPGB(v)Erem+1.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More