multiple-source shortest paths

input: a directed planar embedded graph $\text{[math]}$ with a desginated infinite face $\text{[math]}$ , a vector $\text{[math]}$ assigning lengths to darts, and a shortest-path tree $\text{[math]}$ rooted at one of the vertices of $\text{[math]}$ .
output: a representation of the shortest-path trees rooted at the vertices on the boundary of $\text{[math]}$ .

our goal is to give an algorithm that solves this problem in $\text{[math]}$ time where $\text{[math]}$ is the number of vertices (assuming no parallel edges).

there is an obvious obstacle: each shortest-path tree consists of $\text{[math]}$ edges, so explicitly outputting one for each of the possibly many vertices on the boundary of $\text{[math]}$ could take far more than $\text{[math]}$ time.
to resolve this difficulty, we use a simple implicit representation of the shortest-path trees. let $\text{[math]}$ be the cycle of darts forming the boundary of $\text{[math]}$ where $\text{[math]}$ is the root of the given shortest-path tree $\text{[math]}$ (see [[blk:fig-mssp-4]]). for $\text{[math]}$ , let $\text{[math]}$ be the shortest-path tree rooted at $\text{[math]}$ . we assume that each shortest-path tree $\text{[math]}$ includes only finite-length darts. the algorithm will describe the changes required to transform $\text{[math]}$ into $\text{[math]}$ , the changes needed to transform $\text{[math]}$ into $\text{[math]}$ ,..., and the changes needed to transform $\text{[math]}$ into $\text{[math]}$ . we will show that the total number of changes is at most the number of finite-length darts of $\text{[math]}$ .
/home/mahmooz/brain/pen/1734701863.0895941.xopp

the basic unit of change in a rooted tree $\text{[math]}$ , called a pivot, consists of ejecting one dart $\text{[math]}$ and inserting another dart $\text{[math]}$ so that the result is again a rooted tree. a pivot is specified by the pair $\text{[math]}$ of darts.
transforming $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ consists of

a special pivot that ejects the dart whose head is $\text{[math]}$ (from [[blk:fig-mssp-4]]), and inserts the dart $\text{[math]}$ (now $\text{[math]}$ is $\text{[math]}$ -rooted)) (this is shown in [[blk:fig-mssp-1]]), and
a sequence of ordinary pivots each of which ejects a dart $\text{[math]}$ and inserts a dart $\text{[math]}$ with the same head.

for $\text{[math]}$ , the MSSP algorithm outputs the sequence of pivots that transform $\text{[math]}$ into $\text{[math]}$ . we shall show that the amortized time per pivot is $\text{[math]}$ . the number of special pivots is $\text{[math]}$ . we also show that the number of ordinary pivots is at most the number of finite-length darts. it follows that the running time is $\text{[math]}$ .
/home/mahmooz/brain/pen/1734861345.51882.xopp
[cite:;taken from @graph_klein_2024 chapter 7.2.1 pivots]

to faciliate the exposition we first consider the non-degenerate case, where shortest paths are unique.

let $\text{[math]}$ be a graph, let $\text{[math]}$ be a dart vector, and let $\text{[math]}$ be a dart. for a vertex $\text{[math]}$ , we say $\text{[math]}$ is $\text{[math]}$ -tight with respect to $\text{[math]}$ if $\text{[math]}$ is tight with respect to the from- $\text{[math]}$ distance vector with respect to $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 7.3 contiguity property of shortest-path trees in planar graphs]

there is a $\text{[math]}$ -rooted shortest-path tree containing $\text{[math]}$ iff $\text{[math]}$ is $\text{[math]}$ -tight.
[cite:;taken from @graph_klein_2024 lemma 7.3.1]

note that our unique shortest-paths assumption implies that a dart is $\text{[math]}$ -tight if and only if is in the shortest path tree rooted at $\text{[math]}$ .

let $\text{[math]}$ be a planar embedded graph with infinite face $\text{[math]}$ , and let $\text{[math]}$ be a dart vector. let $\text{[math]}$ be the cycle of darts forming the boundary of $\text{[math]}$ .
for each dart $\text{[math]}$ , the set
$\text{[math]}$ forms a consecutive subsequence of the cycle $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 7.3.2]

/home/mahmooz/brain/pen/1734787377.387264.xopp

the number of pivots required to transform shortest-path tree $\text{[math]}$ into $\text{[math]}$ , summed over all $\text{[math]}$ , is at most the number of finite-length darts.
[cite:;taken from @graph_klein_2024 corollary 7.3.3]

we also need to show how using specific data structures we can find the necessary pivots and apply them in an amortized time of $\text{[math]}$ per pivot.
throughout the algorithm, the tree we construct will always be a shortest-path tree.

for each dart $\text{[math]}$ , there is at most one iteration $\text{[math]}$ such that $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 7.4.1]

by the consecutive-roots lemma, there is at most one integer $\text{[math]}$ such that $\text{[math]}$ is in $\text{[math]}$ but is not in $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 7.4.1]

$\text{[math]}$ is at most the number of darts.
[cite:;taken from @graph_klein_2024 corollary 7.4.2]

we describe how to move from $\text{[math]}$ , the tree rooted at $\text{[math]}$ , to $\text{[math]}$ , the tree rooted at $\text{[math]}$ , while maintaining a shortest-path tree.
consider $\text{[math]}$ , this is a shortest-path tree for $\text{[math]}$ , let $\text{[math]}$ denote the distance from $\text{[math]}$ to $\text{[math]}$ . to convert $\text{[math]}$ to a tree rooted at $\text{[math]}$ , we insert into the tree the dart $\text{[math]}$ and throw out the dart in $\text{[math]}$ whose head is $\text{[math]}$ . the tree we receive $\text{[math]}$ will not be a shortest-path tree for $\text{[math]}$ , but if we modify the length of the dart $\text{[math]}$ to be $\text{[math]}$ , it will become a shortest-path tree. this is demonstrated in [[blk:fig-mssp-1]].
a procedure $\text{[math]}$ called in the algorithm consists of a loop, each iteration of which selects a dart to add to $\text{[math]}$ and a dart to remove from $\text{[math]}$ . we show later that setting up the loop takes $\text{[math]}$ time, the number of iterations is $\text{[math]}$ , and each iteration takes amortized $\text{[math]}$ time. the time for $\text{[math]}$ is therefore $\text{[math]}$ . summing over all $\text{[math]}$ and using cor-mssp-1, we infer that the total time for $\text{[math]}$ and therefore for MSSP is $\text{[math]}$ .
in each iteration, the algorithm determines that a dart $\text{[math]}$ not in $\text{[math]}$ must be added to $\text{[math]}$ . it then pivots $\text{[math]}$ into $\text{[math]}$ , which means

removing from $\text{[math]}$ the dart whose head is $\text{[math]}$ and
adding $\text{[math]}$ to $\text{[math]}$ .

conceptually, $\text{[math]}$ is as follows. let $\text{[math]}$ denote the $\text{[math]}$ -to- $\text{[math]}$ distance in $\text{[math]}$ . to initialize, $\text{[math]}$ temporarily sets the cost of the dart $\text{[math]}$ to $\text{[math]}$ . it then performs a special pivot, removing from $\text{[math]}$ the dart whose head is $\text{[math]}$ , and inserting $\text{[math]}$ into $\text{[math]}$ . it then gradually increases the cost of $\text{[math]}$ to its original cost while performing ordinary pivots as necessary to maintain that $\text{[math]}$ is a shortest-path tree.
after the initialization, the procedure uses a variable $\text{[math]}$ to represent the current modified cost of $\text{[math]}$ . the costs of other darts remain unmodified. let $\text{[math]}$ denote the vector of costs. that is,
$\text{[math]}$ under these costs, the cost of the path in $\text{[math]}$ to a vertex $\text{[math]}$ is denoted $\text{[math]}$ . the vector $\text{[math]}$ is not represented explicitly by the algorithm; we use it in the analysis and proof of correctness.
after initialization, the procedure $\text{[math]}$ repeats the following two steps until $\text{[math]}$ equals the original cost of $\text{[math]}$ :

increase $\text{[math]}$ until any further increase would result in some dart $\text{[math]}$ becoming tense with respect to $\text{[math]}$ and $\text{[math]}$ .
pivot $\text{[math]}$ into $\text{[math]}$ .

this operation is demonstrated in [[blk:fig-mssp-3]].
[cite:;taken from @graph_klein_2024 chapter 7.5 changeroot: the inner loop of the mssp algorithm]

/home/mahmooz/brain/pen/1734868601.2591472.xopp
by having that the initial value of the dart in the special pivot is $\text{[math]}$ , its as if we never moved from $\text{[math]}$ to $\text{[math]}$ in terms of distances from $\text{[math]}$ to other nodes, so the tree $\text{[math]}$ will be a shortest-path tree still (with respect to both $\text{[math]}$ and $\text{[math]}$ ), but we need to gradually increase $\text{[math]}$ while conducting normal pivots.

throughout the execution, $\text{[math]}$ is a shortest-path tree with respect to the costs $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 7.5.1]

the algorithm pivots in a dart $\text{[math]}$ only if necessary, i.e. if continuing the shrinking or growing phase without pivoting in $\text{[math]}$ would result in $\text{[math]}$ not being a shortest-path tree, in particular if $\text{[math]}$ would become tense with respect to $\text{[math]}$ and $\text{[math]}$ . a dart $\text{[math]}$ is in danger of becoming tense only if its slack cost with respect to $\text{[math]}$ is decreasing.

how do we know which darts need to be inserted into $\text{[math]}$ and when? we check the length of every dart $\text{[math]}$ not in $\text{[math]}$ , how much longer the path $\text{[math]}$ is than $\text{[math]}$ ( $\text{[math]}$ denotes the path from the root to $\text{[math]}$ in $\text{[math]}$ ). this difference in length we call the slack of $\text{[math]}$ with respect to $\text{[math]}$ , and denote it by $\text{[math]}$ where $\text{[math]}$ denotes the length of the path $\text{[math]}$ :
$\text{[math]}$ when we add $\text{[math]}$ to the cost of $\text{[math]}$ , we consider what happens to $\text{[math]}$ :

if $\text{[math]}$ and $\text{[math]}$ are descendants of $\text{[math]}$ in $\text{[math]}$ , the slack doesnt change,
if $\text{[math]}$ and $\text{[math]}$ arent descendants of $\text{[math]}$ in $\text{[math]}$ , the slack doesnt change,
if $\text{[math]}$ is a descendant of $\text{[math]}$ and $\text{[math]}$ isnt, the slack increases by $\text{[math]}$ ,
if $\text{[math]}$ isnt a descendant of $\text{[math]}$ and $\text{[math]}$ is a descendant of $\text{[math]}$ , the slack decreases by $\text{[math]}$ .

we shift $\text{[math]}$ into the tree when its slack becomes cost becomes 0. since $\text{[math]}$ is a shortest-path tree, the slack cost of every edge that isnt in $\text{[math]}$ isnt negative, thus it suffices to keep track of the edges whose tails are in the subtree of $\text{[math]}$ and whose heads are in the subtree of $\text{[math]}$ . those are exactly the edges in the fundamental cycle of $\text{[math]}$ with respect to $\text{[math]}$ . in other words, these are the edges in the path from the face $\text{[math]}$ to the face $\text{[math]}$ . all we have to do (if at all), is to track the slack costs of the edges in the path from $\text{[math]}$ to $\text{[math]}$ in $\text{[math]}$ , all those edges arent in $\text{[math]}$ , which means they are in $\text{[math]}$ . the slack of all of those edges decreases by $\text{[math]}$ when we increase the length of $\text{[math]}$ by $\text{[math]}$ , thus the first dart whose slack cost reaches 0 is the the dart with minimal slack cost, hence to apply a pivot we need to:

find the dart whose slack cost in minimal in the path $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ in $\text{[math]}$ . let $\text{[math]}$ be the dart, and $\text{[math]}$ be its slack cost,
subtract $\text{[math]}$ from the slack cost of all the darts in $\text{[math]}$ (on the path from $\text{[math]}$ to $\text{[math]}$ ), add $\text{[math]}$ to the slack cost of all darts in $\text{[math]}$ (on the path from $\text{[math]}$ to $\text{[math]}$ ), an add $\text{[math]}$ to the length of the dart $\text{[math]}$ .
remove the edge of $\text{[math]}$ whose head is $\text{[math]}$ from $\text{[math]}$ and insert $\text{[math]}$ into $\text{[math]}$ .

this process needs to be applied as long as $\text{[math]}$ hasnt yet returned to its original cost.

[cite:;taken from @graph_klein_2024 chapter 7 multiple-source shortest paths]

we can build a data structure for mssp that answers queries from a boundary vertex to any other vertex in $\text{[math]}$ time, where $\text{[math]}$ is the length of the shortest path to the destination vertex.
[cite:;refer to @graph_klein_2024 chapter 7.9 using the output of the mssp algorithm]