# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm  
Whenever we use arrays in our algorithms, we will use an operator \([\cdot]\) to access its elements. To be able to do this on arrays that are indexed according to the nodes or the arcs of \(G\), we assume that these have unique ids from \(0\) to \(|V|-1\) and from \(0\) to \(|A|-1\), respectively. Then, if for example \(\Delta\) is an array with one entry per arc in \(G\), \(\Delta[a]\) denotes the content of \(\Delta\) at the position specified by the id of the arc \(a\in A\). Paths and Labels  
In Algorithm 1, paths are considered according to the lexicographically increasing costs. A point \(x\in\mathbb{R}^{d}_{\geq 0}\) is said to be lexicographically smaller than a point \(y\in\mathbb{R}^{d}_{\geq 0}\) (\(x<_{lex}y\)) if and only if \(x_{i}<y_{i}\) in the first dimension \(i\in\{1,\ldots,d\}\) in which \(x_{i}\
eq y_{i}\), and we say that a path \(p\) is lexicographically smaller than another path \(p^{\prime}\) if \(c(p)<_{lex}c(p^{\prime})\). We will store paths using labels, i.e., by an implicit representation. Let \(p\) be an \((s,v)\)-path (starting at \(s\) with costs \(\tau_{0}\)) whose last arc is \((u,v)\in A\). The label corresponding to \(p\) is a tuple \(\ell=(v,\ell_{\ell}:=c(p),\ell_{u})\), where \(\ell_{u}\) is a pointer to the label representing the \((s,u)\)-subpath of \(p\). Note that \(c_{\ell}=\hat{c}_{(u,v)}(c_{\ell_{u}})\), which, incurring in an abuse of notation that increases the readability, can be put as \(c_{\ell}=\hat{c}_{(u,v)}(\ell_{u})\). For every node \(v\in V\) the set  
Figure 1: Graph corresponding to the Dyn-MOSP instance discussed in Examples 1 and 2. The corresponding arc cost functions are shown in Figure 2.  
Figure 2: These plots show the two arc cost functions corresponding to the three arcs of the graph in Figure 1: the leftmost functions correspond to the arc \(a_{1}=(u,w)\); the functions in the middle to the arc \(a_{2}=(v,w)\); the rightmost functions to the arc \(a_{3}=(w,x)\). contains the labels corresponding to the efficient \((s,v)\)-paths found during the algorithm. We will see that the label sets \(L_{v}\) will only increase; a label \(\ell\in L_{v}\) is therefore also called a permanent label. Additionally, a lexicographically sorted priority queue \(Q\) stores at most one tentative label per node. Tentative labels correspond to paths that have been explored during the algorithm but are not yet known to be efficient. For a node \(v\), the label stored in \(Q\) corresponds to the lexicographically minimal \((s,v)\)-path that has not yet been made permanent and is not dominated by any label in \(L_{v}\) (we write \(L_{v}\
leqq L_{v}\)). ```
Input : Digraph \(G=(V,A)\), Arc Costs \(c:A\to\mathbb{F}^{d}\), Node \(s\in V\), Initial costs \(\tau_{0}\in\mathbb{R}_{\geq 0}^{d}\). Additional FPTAS Input : Vector of approximation ratios \(\epsilon\in\mathbb{R}_{\geq 0}^{d-1}\). // The output is a minimum complete set in the exact scenario and a \((1+\epsilon)\)-cover (see Section 4) if the algorithm is used as an FPTAS. Output : Labels \(L:=\bigcup_{v\in V}L_{v}\). 1 Prio. Queue \(Q\leftarrow\emptyset\);
2 for\(v\in V\)do Permanent labels \(L_{v}\leftarrow\emptyset\) ; for\(a\in A\)do\(lastProcessLabel[a]\gets 0\); Label \(l_{init}\leftarrow(s,\tau_{0},\texttt{NULL})\); /* Only for MD-A. +/ Label \(l_{init}\leftarrow(s,\tau_{0},\texttt{NULL},\texttt{pos}\left(\tau_{0}\right))\); /* Only for MD-FPTAS. +/ \(Q\gets Q\cup\{l_{init}\}\); \(L_{s}\leftarrow L_{s}\cup\{l_{init}\}\); while\(Q\
eq\emptyset\)do
3 Label \(\ell_{v}^{*}\equiv(v,\,c_{\ell_{v}},\,\ell_{pred})\leftarrow\) Label with lexicographically minimal costs in \(Q\); \(L_{v}\gets L_{v}\cup\{\ell_{v}^{*}\}\) ; /* Make \(\ell_{v}\) permanent. +/ \(\ell_{v}^{\texttt{new}}\gets nextCandidateLabel(v,lastProcessLabel, \cup_{u\in\delta^{-}(v)}L_{u})\) ; /* Only for MD-A.