# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
+/ \(\ell_{v}^{\texttt{new}}\gets nextCandidateLabel(v,lastProcessLabel, \cup_{u\in\delta^{-}(v)}L_{u},\epsilon)\); if\(\ell_{v}^{\texttt{new}}\
eq\texttt{NULL}\)then\(Q\gets Q\cup\{\ell_{v}^{\texttt{new}}\}\) ; for\(w\in\delta^{+}(v)\)do
4\(Q\gets propagate(\ell_{v}^{*},w,Q,L_{w})\) ; /* Only for MD-A. +/ \(Q\gets propagate(\ell_{v}^{*},w,Q,L_{w},\epsilon)\); /* Only for MD-FPTAS. +/ return\(L_{v}\) for all \(v\in V\);
```  
**Algorithm 1**Multiobjective Dijkstra Algorithm (MD-A)  
We present the pseudocode of Algorithm 1 in an abstract way, i.e., without specifying the partial order used to define dominance. Instead, we call a function BLACK_BOX_DOM that returns TRUE only if a newly found candidate path is dominated by the set of permanent paths at a node, i.e., if this set contains a path that dominates the candidate path. This allows us to use the same pseudocode for the exact algorithm presented in this section and for the MD-FPTAS presented in Section 4. Algorithms 2 and 3 show the function BLACK_BOX_DOM used for the exact MD-A. ```
1 return\(L_{v}[|L_{v}|-1]\leq_{D}\ell_{v}\)
```  
**Algorithm 2**BLACK_BOX_DOM(\(L_{v},\ell_{v}\)) for MD algorithm, \(d=2\). ```
1 for\(\ell\in L_{v}\)do
2 if\(\ell\preceq_{D}l_{v}\)thenreturn TRUE; return FALSE
```  
**Algorithm 3**BLACK_BOX_DOM(\(L_{v},\ell_{v}\)) for MD algorithm, \(d\geq 3\). ```
1 for\(\ell\in L_{v}





**Example 2**. : _Going back to the example shown in Figure 2, assume that the labels \(\ell\) with costs \(\tau\) at \(u\) and \(\ell^{\prime}\) with costs \(\tau^{\prime}\) at \(v\) are in the queue \(Q\) and \(\tau<_{lex}\tau^{\prime}\). Then, \(\ell\) is extracted earlier from \(Q\) and in the same iteration, Procedure propagate is called to extend \(\ell\) along the arc \(a_{1}=(u,w)\) and obtain the tentative label \(\ell_{w}=(w,\tau_{w}=\hat{c}_{(u,w)}(\tau),\ell)\). We assume that no label for \(w\) exists, neither in \(Q\) nor in \(L_{w}\), and hence, \(\ell_{w}\) is added to \(Q\). Suppose that in the next iteration of Algorithm 1, the label \(\ell^{\prime}\) with costs \(\tau^{\prime}\) at \(v\) is extracted. During its extension towards \(w\) in propagate, the label \(\ell^{\prime}_{w}=(w,\tau^{\prime}_{w}=\hat{c}_{(v,w)}(\tau^{\prime}),\ell^{ \prime})\) is created. As we can see in the rightmost plot in Figure 2, \(\tau^{\prime}_{w,1}<\tau_{w,1}\) and hence, \(\tau^{\prime}_{w}<_{lex}\tau_{w}\). Since the conditions in Lines 3 and 6 of propagate are fulfilled, the label \(\ell_{w}\) is replaced by \(\ell^{\prime}_{w}\), which becomes the new label for \(w\) in \(Q\). This however does not discard \(\ell_{w}\)! Some iterations later, \(\ell^{\prime}_{w}\) is extracted from \(Q\) and in the same iteration, nextCandidateLabel is called to build a new tentative label for \(w\) in \(Q\) out of the permanent labels of the predecessor nodes of \(w\). It is in this search where \(\ell_{w}\) is found again and since it is not dominated (Line 8 of nextCandidateLabel) by any permanent label at \(w\) (currently \(L_{w}\) only contains \(\ell^{\prime}\)), it is added to \(Q\). Indeed, as shown in the rightmost plot in Figure 2, \(\tau_{w}\
ot\preceq_{D}\tau^{\prime}_{w}\) and \(\tau^{\prime}_{w}\
ot\preceq_{D}\tau_{w}\) meaning that both labels have to be added to \(L_{w}\). Later, the label with costs \(\tau_{w}\) is extracted from \(Q\) and finally made permanent. The extension of both labels towards \(x\) along \((w,x)\) works in the same way._

### Correctness

As noted in the beginning of the section, we require the arc cost functions \(c_{a,i}\), to fulfill the FIFO property:

**Definition 3** (First-In-First-Out Property). : _The in cost function \(c_{a,i}\) of an arc \(a\in A\) fulfills the FIFO property if and only if for two cost components \(\tau_{i}\), \(\tau^{\prime}_{i}\) with \(\tau_{i}<\tau^{\prime}_{i}\), there holds \(\hat{c}_{a,i}(\tau_{i})\leq\hat{c}_{a,i}(\tau^{\prime}_{i})\)._

The correctness of Algorithm 1 relies on the Bellman-Principle [22] of optimality.