Breaking_the_Bellman-Ford_Shortest-Path_Bound

Download as pdf or txt
Download as pdf or txt
You are on page 1of 12

Breaking the Bellman-Ford Shortest-Path Bound ∗

Amr Elmasry
Egypt University of Informatics and Alexandria University
amr.elmasry@eui.edu.eg and elmasry@alexu.edu.eg
arXiv:2410.23383v1 [cs.DS] 30 Oct 2024

In this paper we give a single-source shortest-path algorithm that breaks, after over 65 years,
the O(n · m) bound for the running time of the Bellman-Ford-Moore algorithm, where n is the
number of vertices and m is the number of arcs of the graph. Our algorithm √ converts
pthe input
graph to a graph with nonnegative weights by performing at most min(2 · n, 2 · m/ log n)
calls to a modified version of Dijkstra’s algorithm, such that the shortest-path trees are the same
for the new graph as those for the original. When Dijkstra’s algorithm√ is implemented
√ using
Fibonacci heaps, the running time of our algorithm is therefore O( n · m + n · m log n).

keywords: Combinatorial algorithms, Shortest paths, Labeling methods, Dijkstra’s algorithm,


Negative arcs, Negative cycles

1 Introduction
The shortest-path problem is one of the classical topics in graph algorithms. Consider a directed
weighted graph G = (V, A), V is the list of n vertices, A is the list of m arcs, and ℓ : A → R
is a length function, where ℓ(u, v) is the weight of the arc (u, v). A shortest path between two
vertices is a path of arcs with the minimum total weight. The single-source version is to find
the shortest paths from a given source s to all other vertices. The shortest path is undefined if
G has a cycle with negative total weight accessible from the source. The objective is to get a
shortest-path tree from s to all the vertices in G, or to alert that G has a negative cycle.
Since Bellman [2], Ford [12], and Moore [20] have developed their O(n · m) shortest-path
algorithm, several attempts were unsuccessful to break this asymptotic worst-case bound, except
for some special cases. Nevertheless, several heuristics were developed to outperform the Bellman-
Ford-Moore algorithm in practice, still not surpassing the theoretical bound. These algorithms
include [10, 17, 22, 23, 27]. If the graph contains cycles of negative weight, all the aforementioned
algorithms would report it but most likely not as soon as possible. In the literature there are
several algorithms with the primary objective of promptly detecting if a negative cycle exists
[4, 5, 18, 27, 29]. The asymptotic worst-case running times of all these algorithms are at least as
the Bellman-Ford bound. Other algorithms that allow negative arc weights, but whose running
times depend on the weights of the arcs, rely on√a technique called scaling [6, 14, 16]. Most
notable is Goldberg’s algorithm that runs in O( n · m log N ) time, where N is the absolute
value of the largest negative arc weight [16]. The well-known Dijkstra algorithm only works
efficiently for graphs with nonnegative arc weights [8]. Dijkstra’s algorithm when implemented
using Fibonacci heaps runs in O(m + n log n) time [13]. If there are arcs with negative weights,
Dijkstra’s algorithm can be used but without a polynomial-time guarantee. Some suggestions
[9, 21] are to handle the problem by repeatedly applying Dijkstra’s algorithm to a series of
subgraphs of the original. Such algorithms are referred to as Dijkstra-based algorithms. The
running times of the Dijkstra-based algorithms depend on the number of negative arcs and their
∗ This paper is based upon work supported by Science, Technology, & Innovation Funding Authority (STDF)

under grant number 45542

1
distribution within the graph. In particular, the algorithm in [9] calls Dijkstra’s algorithm at most
k + 2 times, where k is the maximum number of negative arcs on a path of the shortest-path tree.
When the number of negative arcs is large, the performance of these Dijkstra-based algorithms
degrades and they cannot compete with the other aforementioned algorithms in practice.
On the other hand, more efficient shortest-path algorithms with better theoretical bounds
exist for some special graph families like: planar graphs [19] and Euclidean graphs [24]. If the arc
weights are nonnegative integers, special priority queues were developed to solve the shortest-
path problem more efficiently, depending on the weights of the arcs [1, 28]. Most notable is that
the single-source shortest-path problem can be solved in O(n + m) time for acyclic graphs using
topological sorting [7].
Recently, Fineman [11] introduced a randomized single-source shortest-path algorithm that
runs in expected Õ(m · n8/9 ) time. Our algorithm is deterministic and asymptotically faster.
In this paper we introduce a new algorithm for the single-source shortest-path problem break-
ing the O(n · m) time bound that endured over 65 years. Our algorithm repeatedly calls: i) a
linear-time shortest-path algorithm for an acyclic graph with nonpositive weights and ii) Dijk-
stra’s algorithm on a graph with nonnegative weights. Afterwards, the original graph is trans-
formed to a graph with nonnegative weights that has the same shortest-path trees as the original
graph. One more call to Dijkstra’s
√ algorithm
√ on this transformed graph would then finish the
job. Our algorithm runs in O( n · m + n · m log n) time.
We have implemented our algorithm to anticipate its performance in practice, and ran it on
a large set of test cases. Experimental results indicate that our algorithm is practically efficient,
and much faster than all the competitors. We shall report these results later in a separate study.

2 Background
2.1 Label correcting methods
Most shortest-path algorithms are based on the general label-correcting method [3, 7, 15, 25]. For
every vertex u, the method maintains a potential value d[u] (tentative distance from the source
s) and a parent pointer p[u], and update them throughout the algorithm. The method starts by
setting d[s] = 0; and for every other vertex: d[u] = ∞, p[u] = nil.
The scan operation, defined on a vertex u, checks all outgoing arcs from u for relaxation. For
every vertex v in the adjacency list of u, u.adj[ ], the arc (u, v) is relaxed if d[v] > ℓ(u, v) + d[u]
by setting d[v] ← ℓ(u, v) + d[u] and setting p[v] ← u. The method works in rounds until no
more arcs can be relaxed. For each round, the scan operation is applied to some and possibly
all the vertices. Different strategies for selecting which vertices to be scanned and their scanning
order lead to different algorithms. When the algorithm terminates, if G has no negative cycles,
the final value d[u] for every vertex u is the shortest-path distance from s to u, and the parent
pointers constitute a shortest-path tree. If G has negative cycles, the label-correcting method
can be easily modified to find such a cycle and terminate.

2.2 The Bellman-Ford-Moore algorithm


The Bellman-Ford-Moore algorithm scans, in each round, all the vertices of the graph in arbitrary
order. Other than the source vertex, the number of vertices with correctly settled potentials is at
least i after the i-th round. In accordance, if there are no negative cycles, the shortest paths are
correctly computed after at most n − 1 rounds. The running time of the algorithm is O(n · m).

2.3 Dijkstra’s algorithm


Dijkstra’s algorithm [8] is a label-correcting method that works efficiently for graphs with nonneg-
ative arc weights. Each round, the algorithm selects a vertex with the minimum potential value
among the unscanned vertices to be scanned next. For graphs with nonnegative arc weights, once

2
Implementation 1 The Bellman-Ford-Moore Algorithm
for all u ∈ V do
d[u] ← ∞
p[u] ← nil
end for
d[s] ← 0
repeat n − 1 times
for all (u, v) ∈ A do
if d[v] > ℓ(u, v) + d[u] then
d[v] ← ℓ(u, v) + d[u]
p[v] ← u
end if
end for

a vertex is scanned it need not be scanned again. The worst-case complexity of Dijkstra’s algo-
rithm in this case depends on the data structure used for finding the vertex with the minimum
potential value: when implemented using arrays or linked lists, the algorithm runs in O(n2 ) time;
when implemented using binary heaps, the algorithm runs in O(m lg n) time; when implemented
using Fibonacci heaps, the algorithm runs in O(m + n lg n) time [13]. We use the subroutine
Create-Priority-Queue(V, d) to initialize a priority queue (heap) Q with the items in the list of
vertices V using the corresponding values in a list of potentials d. The subroutine Extract-Min(Q)
returns the item with the minimum value in Q. The subroutine Decrease(Q, v, d[v]) decreases
the value corresponding to the vertex v in Q to its new potential value d[v].

Implementation 2 Dijkstra’s Algorithm


for all u ∈ V do
d[u] ← ∞
p[u] ← nil
end for
d[s] ← 0
Q ← Create-Priority-Queue(V, d)
while Q is not empty do
u ← Extract-Min(Q)
for all v ∈ u.adj[ ] do
if d[v] > ℓ(u, v) + d[u] then
d[v] ← ℓ(u, v) + d[u]
p[v] ← u
Decrease(Q, v, d[v])
end if
end for
end while

2.4 Shortest paths for acyclic graphs


Topological sorting of an acyclic graph is to produce a linear ordering of the vertcies of the graph
where u appears before v if (u, v) is an arc in the graph. This can be done by keeping track of a
list L of the vertices having no ingoing arcs. At every iteration, an arbitrary vertex is removed
from L and appended to the output, and subsequently all the arcs outgoing from this vertex are
removed from the graph and L is updated in accordance [7]. As the resulting graph is always
acyclic, there is at least one vertex in L until all the vertices are ordered. We use the subroutine
Vertices-Topological-Sort(G) to produce such an ordering from an acyclic graph G.

3
The shortest paths in an acyclic graph with n vertices and m arcs, even with negative arcs,
can then be found in O(n + m) time using topological sorting [7]. Once the topological ordering
is available, the vertices are scanned in order to find the shortest path distances.

Implementation 3 Acyclic-Shortest-Paths
for all u ∈ V do
d[u] ← ∞
p[u] ← nil
end for
d[s] ← 0
Q ← Vertices-Topological-Sort(G)
while Q is not empty do
u ← dequeue(Q)
for all v ∈ u.adj[ ] do
if d[v] > ℓ(u, v) + d[u] then
d[v] ← ℓ(u, v) + d[u]
p[v] ← u
end if
end for
end while
return(G)

2.5 Potentials and reduced weights


Given a list of potential values d corresponding to the list of vertices V , the reduced weight
ld : A → R for an arc (u, v) ∈ A is defined
ℓd (u, v) = ℓ(u, v) + d[u] − d[v].
Let Gd be the graph G with the reduced weights instead of the originals, and call it the reduced-
cost graph. For any path P = hu0 , u1 , . . . , uk i in G, let ℓ(P ) = ki=1 ℓ(ui−1 , ui ) and ℓd (P ) =
P
Pk
i=1 ℓd (ui−1 , ui ). For a path P , it directly follows that ℓd (P ) = ℓ(P ) + d[u0 ] − d[uk ]. Hence, the
shortest path between any two vertices is the same for the graph G and the reduced-cost graph
Gd . For a cycle C, ℓd (C) = ℓ(C). Hence, the graph G has a negative cycle if and only if Gd has
a negative cycle. Our objective is to find the potentials that make the reduced weights for Gd
all nonnegative. Once the reduced-cost graph has no negative weights, we can apply Dijkstra’s
algorithm to get the shortest-path tree from the given source. This tree is also the shortest-path
tree for the original graph.

2.6 The admissible subgraph and zero cycles


A subgraph of the original graph G that only includes the arcs with the nonpositive reduced
weights is called the admissible subgraph G− . Typically, if there is a cycle in the admissible
subgraph, then there is a negative cycle in the original graph. The only exception is for a cycle
with zero total weight, i.e., all its arcs have zero weight. In this case, since all the vertices on a
zero cycle have the same shortest-path values, we aim to get rid of those cycles. As in [16], we can
contract the vertices of the zero cycles after identifying those cycles in linear time by finding the
strongly connected components of G− [26]. If there is a negative arc that connects two vertices
of a strongly connected component of G− , a negative cycle is found. We would therefore assume
in the sequel that the zero cycles are first removed by our algorithm, and hence the admissible
subgraph G− is acyclic as long as G has no negative cycle. Once we come up with potentials for
the contracted graph resulting in nonnegative reduced weights for all the arcs, the reduction can
be directly extended to the original graph.

4
3 Preliminaries
3.1 Snakes
In a graph with negative arc weights, we define a snake as a maximal-length segment that has
zero or more consecutive arcs with zero weight followed by one arc with negative weight. The
zero-weight arcs form the tail of the snake, and the negative arc is its head. Obviously, if the
target vertex of the head of a snake touches its tail, it forms a negative cycle. The length (size)
of a snake is the number of arcs it contains. A snake is uniquely identified by its head, and may
share parts of its tail with other snakes. We call a segment with nonnegative arcs, that are not on
a snake’s tail, a passive segment. In general, any path is composed of consecutive snakes possibly
alternating with passive segments.
Throughout our algorithm, as a result of applying different potential values, the reduced
weights on the arcs change, and accordingly the snakes in the reduced-cost graph would be
dynamically changing their positions, lengths, and may as well disappear. Initially, every negative
arc is a head of a snake. We call the negative arc in the input graph where a snake originates at
the beginning of the algorithm, the origin of the snake. If the reduced weight of the head of a
snake becomes zero and that of a succeeding arc becomes negative, while those of the other arcs of
its tail are still zeros, we say that the snake expands. A snake may expand on several succeeding
arcs simultaneously forming several snakes. If the reduced weight of the head of a snake becomes
zero as well as the arcs of a succeeding passive segment up to the tail of another snake, we say that
the first snake connects to the latter snake forming one larger snake. Alternatively, if the reduced
weight of the head of a snake becomes zero and the succeeding arc on a path is nonnegative, the
snake becomes a passive segment on that path. If the snake becomes a passive segment on all
the outgoing paths, we say that the snake vanishes. With every iteration of our algorithm, every
snake in the reduced-cost graph may: expand, connect to another snake, or vanish.

3.2 Insights
The goal of our algorithm is to come up with a list of potential values such that the resulting
reduced-cost graph would have no negative arcs, or otherwise the graph is shown to have a neg-
ative cycle. The potential values are initialized to zeros. Every iteration, some of the potentials
are changed implying changes in the reduced-cost graph. In accordance, the negative weights
are gradually pushed forward through different paths of the reduced-cost graph until they are
mended, or until a negative cycle is discovered
√ p if exists. The good news is that all the negative
weights disappear in at most min(2 · n, 2 · m/ log n) iterations.
We shall use shortest-path computations to perform this task of pushing the negative weights
forward, and hence eliminating them allover the graph. It is possible to find the shortest paths
within the admissible subgraph in linear time as it is acyclic (assuming that the graph has no
negative cycles). It is also possible to efficiently find shortest paths for a graph with nonnegative
weights using Dijkstra’s algorithm. We apply the two procedures alternately and repeatedly.
Before the end of every iteration, since the negative weights are obstacles for the upcoming calls
of Dijkstra’s algorithm, we need to gradually mend these negative weights. In accordance, we use
the potential values to replace the current weights with the reduced weights, and subsequently
reset the potentials to zeros. Evidently, the weights change with every iteration.
Consider the graph G′ formed by adding an artificial source vertex s′ with zero-weight arcs
from s′ to the source vertices of the origins of the snakes in G. Let T be the shortest-path tree
in G′ from s′ . Let δ[x] be the value of the shortest path in T from s′ to vertex x. The graph G
can be converted to a graph with nonnegative weights having the same shortest-path trees when
setting the potential value for every vertex x as d[x] ← min{δ[x], 0} and replacing the actual
weights by the nonnegative reduced weights, as indicated by the next lemma.
Lemma 1. By setting the potential value of every vertex x to d[x] ← min{δ[x], 0}, the reduced
weights of all the arcs are nonnegative.

5
Proof. For any arc (u, v) in the graph, the triangle-inequality property for the shortest paths
indicates that δ[v] ≤ ℓ(u, v) + δ[u]. In all the following cases ℓd (u, v) turns out to be nonnegative.
case 1. δ[u] ≤ 0 and δ[v] ≤ 0: we set d[u] ← δ[u] and d[v] ← δ[v]. Hence, ℓd (u, v) =
ℓ(u, v) + d[u] − d[v] = ℓ(u, v) + δ[u] − δ[v] ≥ 0.
case 2. δ[u] ≤ 0 and δ[v] > 0: we set d[u] ← δ[u] and d[v] ← 0. Hence, ℓd (u, v) = ℓ(u, v) +
d[u] − d[v] = ℓ(u, v) + δ[u] ≥ δ[v] > 0.
case 3. δ[u] > 0: It must be the case that ℓ(u, v) ≥ 0, for otherwise an arc (s′ , u) would have
been added in G′ with ℓ(s′ , u) = 0 resulting in δ[u] ≤ 0.
case 3.1. δ[v] ≥ 0: we set d[u] ← 0 and d[v] ← 0. Hence, ℓd (u, v) = ℓ(u, v)+d[u]−d[v] =
ℓ(u, v) ≥ 0.
case 3.2. δ[v] < 0: we set d[u] ← 0 and d[v] ← δ[v]. Hence, ℓd (u, v) = ℓ(u, v) + d[u] −
d[v] = ℓ(u, v) − δ[v] > 0.

While our procedures operate directly on the weights of the graph, the proof follows by tracing
the snakes in the reduced-cost graph. The intuition behind the proof is as follows. If there are
no negative cycles, the negative weights are pushed forward on the paths of the shortest-path
tree T until mended, over paths that obviously have at most n − 1 arcs each. In addition,
the nonnegative arcs will remain nonnegative while negative arcs gradually become nonnegative
throughout the algorithm. After applying the first procedure (shortest paths for the admissible
subgraph that is an acyclic graph), the negative reduced weights become nonnegative, while
possible new negative reduced weights appear for the arcs following the paths of the admissible
subgraph. In accordance, every snake of the reduced-cost graph either expands in size or converts
to a passive segment. As a result, the negative arcs are either mended or pushed forward. After
applying the second procedure (Dijkstra’s algorithm on a subgraph with nonnegative weights),
at least the first alive snake with respect to the reduced-cost graph on every path of the shortest-
path tree T either connects to the origin of the next snake forming a larger snake or converts to
a passive segment. As a result, the heads of all the first snakes become farther from s′ .

4 The main procedures


Our algorithm includes three subroutines that are executed consecutively and repeatedly until
the reduced-cost graph has no negative arcs: the expansion procedure, the connection procedure,
and the adjust-weights procedure. Every iteration, the potential values on all vertices are initially
zeros and keep decreasing throughout the iteration.

4.1 The expansion procedure


The first procedure, which we call the expansion procedure, operates on the admissible subgraph
G− . When G has no negative cycles, the admissible subgraph G− is acyclic. The expansion
procedure finds the shortest-path values from the source vertices to every vertex within G− .
To find the shortest-path values in an acyclic graph in linear time, the vertices of the graph
are topologically sorted by the subroutine Vertices-Topological-Sort(G− ) forming a list of vertices
Q. As a precondition to the expansion procedure, the potential values on all the vertices are
set to zeros. The list Q is scanned in order, and for each vertex u in Q and every vertex v
in the adjacency list of u, u.adj[ ], the arc (u, v) is relaxed if d[v] > ℓ(u, v) + d[u] by setting
d[v] ← ℓ(u, v) + d[u].
The rough purpose of this procedure is to simultaneously push all the negative weights at
least one arc forward, and hence expand the snakes of the resulting reduced-cost graph compared
to the original. More precisely, all the negative arcs of the admissible subgraph become nonneg-
ative while their positive immediate-successor arcs, if any, may become negative in return. In
conclusion, every snake either expands or vanishes.

6
procedure Expand(G)
Q ← Vertices-Topological-Sort(G− )
while Q is not empty do
u ← dequeue(Q)
for all v ∈ u.adj[ ] do
if d[v] > ℓ(u, v) + d[u] then
d[v] ← ℓ(u, v) + d[u]
end if
end for
end while
return(G)
end procedure

Lemma 2. Consider any snake when applying the expansion procedure. On any specified path in
the resulting reduced-cost graph, the snake either expands in size or converts to a passive segment.
Proof. Consider the reduced weight of any arc (u, v) in G after applying the expansion procedure.
We have ℓd (u, v) = ℓ(u, v) + d[u] − d[v].
If (u, v) was in G− , the expansion procedure guarantees the shortest-path property on the
arcs of G− implying that d[v] ≤ ℓ(u, v) + d[u], and so ℓd (u, v) ≥ 0. Hence, the reduced weights
of all the arcs that were in G− become nonnegative.
If (u, v) was not in G− , we have ℓ(u, v) > 0. Consider the case where d[u] = 0 after the
expansion procedure, indicating that there is no path in G− with a snake on it ending at u. As
all the potential values are nonpositive by Lemma 1, then d[v] ≤ 0. Hence, ℓd (u, v) ≥ ℓ(u, v) > 0.
The reduced weights of the positive arcs that do not follow a path of G− thus remain positive.
The only case where ℓd (u, v) possibly turns negative after the expansion procedure is if (u, v)
was not in G− and d[u] < 0. In such a case, there is path in G− ending up at u with a snake on
it. As the reduced weights of all the arcs on this path become zeros, the snake turns into a larger
snake whose head is (u, v). On the other hand, if ℓd (u, v) remains positive, this means that any
path with a snake entering u becomes a passive segment.
It is possible that a snake loses a lower part of its tail. Assume that (u, v) was on the tail of a
snake before the procedure, and another ingoing snake connects with the first at vertex v. As a
result, the value of d[v] may decrease and ℓd (u, v) may become positive in accordance. In such a
case, this ingoing second snake connects to the upper part of the first, cutting the lower part of
its tail being a passive segment. As a result, the first snake vanishes and the second expands.

4.2 The connection procedure


Complementing the expansion procedure, the resulting potential values are used in another
shortest-path computation, but now for a graph with nonnegative weights.
In more details, the connection procedure operates on a graph G+ , resulting from G′ by
ignoring the negative arcs (assume that their weights are infinity). Since all the weights of
G+ are nonnegative, we apply a modified version of Dijkstra’s algorithm having the priority
queue Q initialized with the potential values that are the shortest-path values resulting from
the expansion procedure. As is customary with the original algorithm, every iteration Dijkstra’s
algorithm selects the vertex with the minimum potential to be scanned next, using the subroutine
Extract-Min(Q), and if possible decreases the potentials of adjacent vertices in accordance. Once
a vertex is scanned it is not scanned again.
The rough purpose of this procedure is to mend the first arc with negative reduced weight
on every path of the shortest-path tree T . More precisely, the reduced weight of the head of the
first snake on every path of the shortest path tree either becomes zero and connects to the head
of the next snake in one larger snake, or otherwise becomes nonnegative and the snake vanishes.

7
procedure Connect(G)
Q ← Create-Priority-Queue(V, d)
while Q is not empty do
u ← Extract-Min(Q)
for all v ∈ u.adj[ ] do
if ℓ(u, v) ≥ 0 and d[v] > d[u] + ℓ(u, v) then
d[v] ← ℓ(u, v) + d[u]
Decrease(Q, v, d[v])
end if
end for
end while
return (G)
end procedure

Lemma 3. Consider the first snake on each path of the shortest-path tree T when applying the
connection procedure. In the resulting reduced-cost graph, the snake either connects to the next
snake or converts to a passive segment.
Proof. Consider a path P on the shortest-path tree T . The potential values on all the vertices
of the first snake on P are the shortest-path values within this call to the expansion procedure.
These values will not change by the connection procedure, implying that the reduced weight of
any arc (u, v) of these arcs is ℓd (u, v) = ℓ(u, v) + d[u] − d[v] = ℓ(u, v) + δ[u] − δ[v] = 0.
Let x be the target vertex of the head of the first snake on P . We show by induction on
the vertices of P from x up to the first vertex with positive shortest-path value or up to the
source vertex of the head of the next snake on P , whichever closer, that the potential on each of
these vertices will attain its shortest-path value before the vertex is scanned within this call to
the connection procedure. Following the expansion procedure, the potential on vertex x attains
the value of the shortest path to x, i.e. d[x] = δ[x], initially fulfilling the induction hypothesis.
Consider any arc (u, v) on P where ℓ(u, v) ≥ 0. From the shortest-path property, we have
δ[v] = ℓ(u, v) + δ[u] implying that δ[v] ≥ δ[u].
For any vertex v with δ[v] ≤ 0, we have d[v] ≥ δ[v] throughout the algorithm. The case where
d[v] = δ[v] before v is scanned directly fulfills the induction hypothesis. Consider the case where
d[v] > δ[v], indicating that d[v] > δ[u]. Assume that the induction hypothesis is fulfilled up to
vertex u. By the induction hypothesis, vertex u will be scanned only when d[u] = δ[u], which is
shown to be less than d[v]. As the connection procedure chooses the vertex with the minimum
potential value to be scanned in each iteration, vertex u will be scanned before vertex v. Once
vertex u is scanned, the potential on v is settled to d[v] = ℓ(u, v) + d[u] = ℓ(u, v) + δ[u] = δ[v],
also fulfilling the induction hypothesis. In accordance, the potential values on all the vertices
up to the source vertex of the head of the second snake on P will reach their shortest-path
values within this call to the connection procedure, as long as these shortest-path values are
nonpositive. Consequently, for any of the arcs on this segment, ℓd (u, v) = ℓ(u, v) + d[u] − d[v] =
ℓ(u, v) + δ[u] − δ[v] = 0. It follows that the first two snakes on P connect to form one larger
snake in the reduced-cost graph.
For the case where v is the first vertex on P with δ[v] > 0, the connection procedure ends up
with d[u] = δ[u] and d[v] = 0 (by Lemma 1). Since δ[v] > 0 in this case, the shortest-path property
implies ℓ(u, v) + δ[u] > 0. Consequently, ℓd (u, v) = ℓ(u, v) + d[u] − d[v] = ℓ(u, v) + δ[u] > 0. It
follows that the first snake on P converts into a passive segment in the reduced-cost graph.
Lemma 4. The arcs with nonnegative weights before the connection procedure attain nonnegative
reduced weights after the procedure.
Proof. Consider an arc (u, v) where ℓ(u, v) ≥ 0. Every vertex is scanned exactly once within the
connection procedure. When u is scanned, (u, v) is relaxed and d[v] ≤ ℓ(u, v) + d[u] implying

8
ℓd (u, v) ≥ 0. Since all potentials never increase within the connection procedure, the only way
for ℓd (u, v) to presumably end up negative is that d[u] would decrease after u is scanned. For
this to happen, there must exist a vertex q with ℓ(q, u) ≥ 0 such that q is scanned after u. The
connection procedure scans the vertex with the minimum potential in every iteration and only
deals with nonnegative arcs. It follows that the potentials of the scanned vertices form a non-
decreasing sequence. In particular, d[u] ≤ d[q] when q is scanned. But then, relaxing (q, u) would
result in d[u] ← ℓ(q, u) + d[q]. Since ℓ(q, u) ≥ 0, d[u] would never decrease after u is scanned.
This contradiction ensures that ℓd (u, v) ≥ 0 after the procedure.

4.3 Adjusting weights


In this procedure, the current weights of the graph G are replaced with the reduced weights using
the list of potential values d. All the potential values are then reset to zeros. In accordance, the
reduced weights remain the same.

procedure Adjust-Weights(G)
for all (u, v) ∈ E do
ℓ(u, v) ← ℓ(u, v) + d[u] − d[v]
end for
for all u ∈ V do
d[u] ← 0
end for
return(G)
end procedure

Lemma 5. When applying the adjust-weights procedure, after the expansion and the connection
procedures, all the arcs with nonnegative weights before the two procedures remain nonnegative.
Proof. By Lemma 4, when applying the expansion followed by the connection procedures, the
reduced weights of the nonnegative arcs remain nonnegative. Hence, the new weights of these
arcs become nonnegative when using the reduced weights to replace the current weights.

5 The snakes algorithm


The expansion and connection procedures offer great machinery to handle snakes. The former
makes each snake longer or coverts it into a passive segment, while the latter connects the first
surviving snake on each path with the origin of another snake or coverts it into a passive segment.
In combination, the two procedures expand each snake by at least one arc and connect the
first snake to an origin, or otherwise convert the snake to a passive segment. Obviously, we shall
repeatedly execute an interleaved combination of the two procedures until the reduced-cost
√ graph
has no negative weights. We prove that the combination will be executed at most 2n times.

Implementation 4 The Snakes Algorithm


1: for all u ∈ V do
2: d[u] ← 0
3: end for
4: while G still has negative arcs do
5: G ← Expand(G)
6: G ← Connect(G)
7: G ← Adjust-Weights(G)
8: end while

9
Lemma 6. After j − 1 iterations of the algorithm, the length of every snake will be at least j.
Proof. Initially, every negative arc is the head of a snake with length at least 1. By Lemma 2, in
the reduced-cost graph, the length of every alive snake increases with every iteration.
Consider an arc (u, v) where ℓ(u, v) < 0 just before executing the expansion procedure. As a
result of the expansion procedure, by Lemma 2, we get ℓd (u, v) ≥ 0. The only way for the arc
to attain a negative weight at the end of the iteration is that d[u] decreases by the connection
procedure. For this to happen, there must exist another snake that would be extended by the
connection procedure such that its body reachs u resulting in (u, v) being its new head. As a
result, this other snake inherits the head of the fist and is now longer.
In addition, by Lemma 4, no nonnegative arcs turn negative by the connection procedure,
and hence no new snakes are created throughout the algorithm.
Theorem 1. We can convert a graph with negative weights, but no negative cycle, to a graph
that has
√ no negative weights, such that the two graphs have the same shortest-path tree, using less
than 2n calls to a linear-time shortest-path computation for an acyclic graph and to a modified
version of Dijkstra’s algorithm, where n is the number of vertices of the graph.
Proof. We distinguish between two types of snakes in the reduced-cost graph: the snakes that are
the first on the paths of the shortest-path tree T and the other snakes. We show by mathematical
induction that before iteration j the heads of the first snakes are at a distance at least j(j − 1)/2
from s′ on every path of the shortest-path tree T . The hypothesis is obviously true for j = 1.
Assume the hypothesis holds after iteration j − 1 and consider the changes at iteration j.
Obviously, the origin of the second snake on any path follows the head of the first, i.e. at a
distance at least j(j − 1)/2 from s′ by the induction hypothesis. By Lemma 6, the length of
every snake after iteration j − 1 is at least j. By Lemma 3, the connection procedure ensures
that each of the first snakes on every path of T either connects to the second snake forming
one snake or vanishes. The lemma also indicates that the potentials on the vertices of the first
snakes have already reached their shortest-path values, implying that no first snake would ever
be connected to another first snake. Once a negative arc is mended its actual weight will forever
turn nonnegative, as indicated by Lemma 5. This will permit the snakes not to be obstructed
by negative arcs that are already mended. It follows that the heads of the first snakes after the
jth iteration must be at distance at least j(j − 1)/2 + j = j(j + 1)/2 from s′ . The induction
hypothesis then holds after iteration j.
Let j ′ be the number of iterations executed by the algorithm. As there are at most√n levels
on any path in the graph, it follows that j ′ (j ′ + 1)/2 ≤ n indicating that j ′ is less than 2n, and
the algorithm must have been terminated by then with a graph that has no negative arcs.
Corollary 1. We can convert a graph with negative weights to a graph that has all nonnegative
weights,
√ such that the two graphs have the same shortest-path tree starting from any source, using
O( n · m + n3/2 · log n) time when implementing the connection procedure using Fibonacci heaps,
where n is the number of vertices and m is the number of arcs of the underlying graph.

6 Improvement
To improve the worst-case asymptotic running time of the algorithm even further, we execute the
expansion procedure c = ⌈ n log n
m ⌉ times within every iteration of the algorithm. In accordance, the
lengths of the snakes grow by at least this amount in every iteration. In effect, the bound on the
√ q m
number of iterations for the algorithm to terminate would be improved to O(min( n, log n )).

Theorem 2. We can convert a graph with negative weights to a graph that has all nonnegative
weights,
√ such that
√ the two graphs have the same shortest-path tree starting from any source, using
O( n · m + n · m log n) time when implementing Dijkstra’s algorithm using Fibonacci heaps,
where n is the number of vertices and m is the number of arcs of the underlying graph.

10
Implementation 5 The Improved Snakes Algorithm
1: for all u ∈ V do
2: d[u] ← 0
3: end for
4: while G still has negative arcs do
5: repeat⌈ n log n
m ⌉ times
6: G ← Expand(G)
7: G ← Connect(G)
8: G ← Adjust-Weights(G)
9: end while

Proof. If n log n ≤ m, c = ⌈ n log n


⌉ = 1 and the algorithm is the same as before indicating that
√m √
the total running time is O( n · m + n3/2 log n) = O( n · m).
The length of every snake is at least c · j after iteration j − 1. In accordance, the heads of the

first snakes after the jth iteration must pbe at distance pat least c·j(j +1)/2 from s . It follows that
c · j (j + 1)/2 ≤ n indicating that j ≤ 2n/c = O( m/ log n). The running time consumed by
′ ′ ′

the expansion procedure in every iteration is O(m · n log n


m ) = O(n log n). Using Fibonacci heaps,
the running time of the connection procedure per iteration is O(m + n log n).
If n log n > m, the running time per iteration
p is O(n log n). √The total running time of the
algorithm in this case is therefore O(n log n · m/ log n) = O(n · m log n).

References
[1] R.K. Ahuja, K. Mehlhorn, J. Orlin, and R.E. Tarjan, Faster algorithms for the shortest path
problem, J ACM 37 (1990), 213–223.
[2] R. Bellman, On a routing problem, Q Appl Math 16 (1958), 87–90.
[3] D.P. Bertsekas, A simple and fast label correcting algorithm for shortest paths, Networks
23 (1993), 703–709.
[4] B.V. Cherkassky, L. Georgiadis, A.V. Goldberg, R.E. Tarjan, and R.F. Werneck, Shortest-
path feasibility algorithms: An experimental evaluation, ACM J Experimental Algorithmics
(JEA) 14 (2009), Article 7.
[5] B.V. Cherkassky and A.V. Goldberg, Negative-cycle detection algorithms, Math Program
85 (1999), 277–311.

[6] M.B. Cohen, A. Madry, P. Sankowski, and A. Vladu, Negative-weight shortest paths and
unit capacity minimum cost flow in Õ(m10/7 log W ) time, Proc Twenty-Eighth Ann ACM-
SIAM Symp Discr Algorithms, SIAM 2017, pp. 752–771.
[7] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, MIT
Press, 3rd edition 1998.

[8] E.W. Dijkstra, A note on two problems in connexion with graphs, Numer Mathematik 1
(1959), 269–271.
[9] Y. Dinitz and R. Itzhak, Hybrid Bellman-Ford-Dijkstra algorithm, J. Discr Algorithms 42
(2017), 35–44.
[10] A. Elmasry and A. Shokry, A new algorithm for the shortest-path problem, Networks 74
(2019), 16–39.

11
[11] J.T. Fineman, Single-source shortest paths with negative real weights in Õ(mn8/9 ) time,
Proc 56th Ann ACM Symp Theory Comput, STOC 2024, Vancouver, BC, Canada, June
24-28, , ACM, 2024, pp. 3–14.
[12] L.R. Ford and D.R. Fulkerson, Flows in Networks, Princeton U. Press, Princeton, NJ, 1962.
[13] M.L. Fredman and R.E. Tarjan, Fibonacci heaps and their uses in improved network opti-
mization algorithms, J ACM 34 (1987), 596–615.
[14] H.N. Gabow and R.E. Tarjan, Faster scaling algorithms for network problems, SIAM J
Comput 18 (1989), 1013–1036.
[15] G. Gallo and S. Pallottino, Shortest path algorithms, Ann Oper Res 13 (1988), 1–79.
[16] A.V. Goldberg, Scaling algorithms for the shortest paths problem, SIAM J Comput 24
(1995), 494–504.
[17] A.V. Goldberg and T. Radzik, A heuristic improvement of the Bellman-Ford algorithm,
Appl Math Lett 6 (1993), 3–6.
[18] D. Goldfarb, J. Hao, and S.R. Kai, Shortest path algorithms using dynamic breadth-first
search, Networks 21 (1991), 29–50.
[19] P.N. Klein, S. Mozes, and O. Weimann, Shortest paths in directed planar graphs with neg-
ative lengths: A linear-space O(n log2 n)-time algorithm, ACM Trans Algorithms 6 (2010),
Article 30.
[20] E.F. Moore, The shortest path through a maze, Volume 3523 of Bell Telephone System.
Technical publications. monograph, 1959.
[21] A. Nakayama and T. Anazawa, Dijkstra-based algorithms for the shortest path problem
with edges of negative length, J Oper Res Soc Jpn 56 (2013), 137–154.
[22] S. Pallottino, Shortest-path methods: Complexity, interrelations and new propositions, Net-
works 14 (1984), 257–267.
[23] U. Pape, Implementation and efficiency of Moore-algorithms for the shortest route problem,
Math Program 7 (1974), 212–222.
[24] R. Sedgewick and J.S. Vitter, Shortest paths in Euclidean graphs, Algorithmica 1 (1986),
31–48.
[25] D.R. Shier and C. Witzgall, Properties of labeling methods for determining shortest path
trees, J Res National Bureau Standards 86 (1981), 317–330.
[26] R.E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Compu 1 (1972),
146–160.
[27] R.E. Tarjan, Shortest paths, Technical Report, AT &T Bell Laboratories, Murray Hill, NJ,
1981.
[28] M. Thorup, On RAM priority queues, SIAM J Comput 30 (2000), 86–109.
[29] C.H. Wong and Y.C. Tam, Negative cycle detection problem, Proc 13th Ann Eur Symp
Algorithms (ESA), Vol. 3669 of Lecture Notes in Computer Science, Springer 2005, pp.
652–663.

12

You might also like