single-source inter-part boundary distances
note that in the following text (and usually in graph theory), 
denotes 
.
denotes .we describe a linear-space, nearly linear-time algorithm that, given a directed planar graph 
with real positive and negative lengths, but no negative cycles, and given a vertex 
, computes single-source shortest paths from 
to all vertices of . if there is a negative cycle, the algorithm should identify it.
using bellman-ford we can achieve a time complexity of
, and hence 
for plane graphs. the algorithm we propose runs in 
, and the best algorithm today runs in 
.
the algorithm triangulates by adding edges with sufficiently large length so that shortest paths are not affected. it then uses the planar-cycle-separator theorem to separate into two parts; an interior subgraph 
and an exterior subgraph 
. the edges and vertices of the cycle separator 
are the only ones that belong to both parts. the vertices 
of are called boundary vertices. since is a simple cycle, it forms the boundary of a single face both in and in . the dense distance graph 
of 
is the complete graph on , where for any 
the length of the arc 
is the length of the 
-to-
path in . the dense distance graphs of its parts.
[cite:;taken from @graph_klein_2024 chapter 8 shortest paths with negative lengths]
with real positive and negative lengths, but no negative cycles, and given a vertex , computes single-source shortest paths from to all vertices of . if there is a negative cycle, the algorithm should identify it.
using bellman-ford we can achieve a time complexity of
, and hence for plane graphs. the algorithm we propose runs in , and the best algorithm today runs in .
the algorithm triangulates
by adding edges with sufficiently large length so that shortest paths are not affected. it then uses the planar-cycle-separator theorem to separate into two parts; an interior subgraph and an exterior subgraph . the edges and vertices of the cycle separator are the only ones that belong to both parts. the vertices of are called boundary vertices. since is a simple cycle, it forms the boundary of a single face both in and in . the dense distance graph of is the complete graph on , where for any the length of the arc is the length of the -to- path in . the dense distance graphs of its parts.
[cite:;taken from @graph_klein_2024 chapter 8 shortest paths with negative lengths]
consider one of the subgraphs 
(
). since all boundary vertices lie on the boundary of a single face of , there is a cyclic clockwise order 
on the vertices in 
(boundary vertices). let 
be the 
weighted incidence matrix of 
. that is, 
equals the 
-to-
distance in . we define the upper triangle of to be the elements of on or above the main diagonal. more precisely, the upper triangle of is the portion 
of . similarly, the lower triangle of consists of all the elements on or below the main diagonal of .
(). since all boundary vertices lie on the boundary of a single face of , there is a cyclic clockwise order on the vertices in (boundary vertices). let be the weighted incidence matrix of . that is, equals the -to- distance in . we define the upper triangle of to be the elements of on or above the main diagonal. more precisely, the upper triangle of is the portion of . similarly, the lower triangle of consists of all the elements on or below the main diagonal of .
for any four indices 
such that either 
and 
are all in 's upper triangle, or are all in 's lower triangle (i.e., either 
or 
), the convex monge property holds:
[cite:;taken from @graph_klein_2024 lemma 8.1.1]
[cite:;taken from @graph_klein_2024 chapter 8.1 total monotonicity and the monge property] such that either and are all in 's upper triangle, or are all in 's lower triangle (i.e., either or ), the convex monge property holds:
[cite:;taken from @graph_klein_2024 lemma 8.1.1]consider the vertices 
of in the order they are shown in [[blk:fig-sssp-2]](a). we claim that 
. since we have a planar graph the meeting point 
of the edges 
is a vertex in the graph, the proof for the claim says that if the path 
is the shortest then it is either the same length as the path 
or shorter, and the same case applies to the path 
with the alternative path 
.
/home/mahmooz/brain/pen/1736876715.7182822.xopp
in the incidence matrix of
, the entries as their occur in [[blk:fig-sssp-2]](a) and [[blk:fig-sssp-2]](b) are shown in [[blk:fig-sssp-2]](c), [[blk:fig-sssp-2]](d), respectively. the matrices we consider will not be monge but their upper and lower triangles will be. if the 4 points shown in the matrices are on the lower triangle as in [[blk:fig-sssp-2]](c) then the monge property holds.
of in the order they are shown in [[blk:fig-sssp-2]](a). we claim that . since we have a planar graph the meeting point of the edges is a vertex in the graph, the proof for the claim says that if the path is the shortest then it is either the same length as the path or shorter, and the same case applies to the path with the alternative path .
/home/mahmooz/brain/pen/1736876715.7182822.xopp
in the incidence matrix of
, the entries as their occur in [[blk:fig-sssp-2]](a) and [[blk:fig-sssp-2]](b) are shown in [[blk:fig-sssp-2]](c), [[blk:fig-sssp-2]](d), respectively. the matrices we consider will not be monge but their upper and lower triangles will be. if the 4 points shown in the matrices are on the lower triangle as in [[blk:fig-sssp-2]](c) then the monge property holds.we present the description of the algorithm for computing shortest paths in the presence of negative arc lengths and no negative length cycles. it consists of five stages. the first four stages alternate between working with negative lengths and working with only positive lengths. let 
be an arbitrary boundary vertex.
the algorithm is also demonstrated in [[blk:fig-sssp-1]].
/home/mahmooz/brain/pen/2025-01-03-Note-14-40.xopp
we describe how to efficiently compute the distances in from to all boundary vertices ([[blk:line-sssp-1]]). the algorithm computes the from- distances in by computing the from- distances in the dense distance graph 
. for 
, the edge lengths of the dense distance grah of have already been computed and stored in 
in the previous step.
be an arbitrary boundary vertex.
- recursive call: the first stage recursively computes the distances from within for
. the remaining stages use these distances in the computation of the distances in . - intra-part boundary-distances: for each graph , the algorithm uses the mssp algorithm to compute all distances in between boundary vertices. this takes
time. - single-source inter-part boundary distances: the algorithm uses a fast implementation of bellman-ford in the dense distance graph of to compute the distances in from to all other boundary vertices.
has 
vertices, so the number of iterations of Bellman-Ford is 
. each iteration consists of relaxing all the edges . because for each , the upper and lower triangles of each has the monge property, all of the edges can be relaxed in 
time. thus this step is implemented in time. - single-source inter-part distances: for each , the distances obtained in the previous stages are used, in a dijkstra computation, to compute the distances in from to all the vertices of . dijkstra's algorithm requires the lengths in to be non-negative, so the recursively computed distances are used as a consistent price vector. this stage takes time. (this stage can actually be implemented in
. this however does not change the overall running time of the algorithm.) - rerooting single-source distances: the algorithm has obtained distances in from . in the last stage these distances are used as a consistent price vector to compute, again using dijkstra's algorithm, distances from in . this stage also requires time.
the algorithm is also demonstrated in [[blk:fig-sssp-1]].
/home/mahmooz/brain/pen/2025-01-03-Note-14-40.xopp
we describe how to efficiently compute the distances in
from to all boundary vertices ([[blk:line-sssp-1]]). the algorithm computes the from- distances in by computing the from- distances in the dense distance graph . for , the edge lengths of the dense distance grah of have already been computed and stored in in the previous step.
let be a directed graph with arbitrary arc lengths. let be a cycle separator in and let and be the external and internal parts of with respect to . let 
and 
be the all-pairs distances between vertices in in and in respectively. let 
be an arbitrary boundary vertex. there exists an algorithm that, given and , computes the from- distances in to all vertices of in 
time and 
space.
[cite:;taken from @graph_klein_2024 theorem 8.3.1]
be a directed graph with arbitrary arc lengths. let be a cycle separator in and let and be the external and internal parts of with respect to . let and be the all-pairs distances between vertices in in and in respectively. let be an arbitrary boundary vertex. there exists an algorithm that, given and , computes the from- distances in to all vertices of in time and space.
[cite:;taken from @graph_klein_2024 theorem 8.3.1]
consider the bellman-ford algorithm on . there are 
vertices, so the number of iterations is . in iteration 
bellman-ford computes for every 
, the quantity 
, which is the length of a shortest -to- path consisting of at most edges of . the following procedure, 
describes this process in detail.
the correctness of follows from the fact that it is an implementation of the bellman-ford algorithm.
to complete the proof it remains to show that can be implemented in 
time. the number of iterations in is . it therefore suffices to show how to implement [[blk:line-sssp-2]] in 
time. this is the crux of the algorithm.
consider the natural clockwise order on the boundary vertices, and regard the tables
, as square -by- matrices. the key observation is that [[blk:line-sssp-2]] can be implemented by computing all column minima of two matrices 
, such that the 
element of 
is 
, and then taking pairwise distances between vertices on a single face of 
. since stores the minimum distances of the two values obtained for each column, it can be decomposed, by lem-sssp-2, into an upper triangular matrix and a lower triangular matrix, both of whom are convex monge. next note that adding a constant to each row of a monge matrix preserves the Monge property. for 
or 
,
implies
hence each matrix decomposes into a lower and an upper triangular convex Monge matrices. the algorithm can therefore find all column minima of each by finding all column minima of each of the two triangular matrices comprising . using the extension to triangular matrices, this can be done in 
time, as desired.
[cite:;taken from @graph_klein_2024 theorem 8.3.1]
[cite:;taken from @graph_klein_2024 chapter 8 shortest paths with negative lengths]. there are vertices, so the number of iterations is . in iteration bellman-ford computes for every , the quantity , which is the length of a shortest -to- path consisting of at most edges of . the following procedure, describes this process in detail.
the correctness of follows from the fact that it is an implementation of the bellman-ford algorithm.
to complete the proof it remains to show that
can be implemented in time. the number of iterations in is . it therefore suffices to show how to implement [[blk:line-sssp-2]] in time. this is the crux of the algorithm.
consider the natural clockwise order on the boundary vertices, and regard the tables
, as square -by- matrices. the key observation is that [[blk:line-sssp-2]] can be implemented by computing all column minima of two matrices , such that the element of is , and then taking pairwise distances between vertices on a single face of . since stores the minimum distances of the two values obtained for each column, it can be decomposed, by lem-sssp-2, into an upper triangular matrix and a lower triangular matrix, both of whom are convex monge. next note that adding a constant to each row of a monge matrix preserves the Monge property. for or ,
implies
hence each matrix decomposes into a lower and an upper triangular convex Monge matrices. the algorithm can therefore find all column minima of each by finding all column minima of each of the two triangular matrices comprising . using the extension to triangular matrices, this can be done in time, as desired.
[cite:;taken from @graph_klein_2024 theorem 8.3.1]