# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
```
1 return\(L_{v}[|L_{v}|-1]\preceq_{\operatorname{pos}}l_{v}\)
```

**Algorithm 4**BLACK_BOX_DOM\((L_{v},\ell_{v})\) for MD-FPTAS, \(d=2\)

The following example shows how efficient labels can be rejected by the MD-FPTAS if they are pos -dominated by permanent labels. **Example 3**. : _Figure 3 visualizes the situation at the end of each of three subsequent iterations of MD-FPTAS. As in Examples 1 and 2, the illustrated graph is a subgraph of a larger graph with \(n=10\) nodes and we set \(\epsilon=0.5\). To illustrate how our FPTAS works, dynamic arc cost functions are not needed. Instead, each arc has \(d=2\) static cost components. Labels are represented only by their cost vector; their correspondence to nodes is made clear by their positioning. The example starts with a permanent label with costs \((80,131)\) at node \(x\) and tentative labels for \(u\) and \(v\) in \(Q\) with costs \((100,100)\) and \((100,101)\), respectively._

_In the first iteration, the label for \(u\) is extracted from \(Q\) and no new candidate label for \(u\) is found. Then, during the propagation of the label \((100,100)\), the resulting label with costs \((120,120)\) at node \(w\) is inserted into \(Q\). In the second iteration, the label with costs \((101,100)\) is extracted from the heap and no new candidate label for \(v\) is found. This label is then propagated to node \(w\), where the resulting tentative label with costs \((140,119)\) is rejected, as \(w\)'s current heap label has costs \((120,120)\) and is lexicographically smaller. So far, the MD-A and the MD-FPTAS would have done exactly the same. In the third iteration, the label with costs \((120,120)\) at node \(w\) is extracted from the heap. When nextCandidateLabel is called, the extension of \(v\)'s permanent label towards \(w\) yields costs \((140,119)\). Hence, it would not be dominated by the new permanent label with costs \((120,120)\) at \(w\) in the exact scenario. However, in the MD-FPTAS, it is rejected since \(120<140\) and \(\operatorname{pos}(120)=107=\operatorname{pos}(119)\). The iteration continues and considers the tentative label with costs \((130,130)\) at node \(x\). It is also rejected despite it would be made permanent in the exact scenario, since \(80<130\) and \(\operatorname{pos}(130)=109=\operatorname{pos}(131)\). The following Lemma holds for any version of Algorithm 1 presented so far. We need it to prove the correctness of the MD-FPTAS. We denote the set of permanent labels at node \(v\) found until iteration \(i\in\{1,\ldots,\mathcal{N}\}\) (including the \(i^{th}\) iteration) by \(L_{v}^{i}\). Thus, \(L_{v}\equiv L_{v}^{\mathcal{N}}\) is used only to denote the final set of permanent labels at \(v\). Lemma 2: _A label \(\ell_{v}\) for a node \(v\in V\) is considered at most \(|L_{v}|+1\) times before it is made permanent or finally discarded. If it is discarded, there is a permanent label in \(L_{v}\) that (\(\operatorname{pos}\)-)dominates \(\ell_{v}\)._

Proof: Let \(\ell_{u}\) be the permanent predecessor label of \(\ell_{v}\) at node \(u\in\delta^{-}(v)\). \(\ell_{v}\) is considered for the first time during a call to propagate in the iteration \(i\in\{1,\ldots,\mathcal{N}\}\) in which \(\ell_{u}\) is extracted from \(H\) and added to \(L_{u}^{i}\). Let \(k\in\{i+1,\ldots,\mathcal{N}\}\) be the next iteration wherein a label \(\ell_{v}^{\prime}\) for node \(v\) is extracted from \(Q\). If \(\ell_{v}^{\prime}=\ell_{v}\), we are done since \(\ell_{v}\) was considered just once before it is made permanent. In case \(\ell_{v}^{\prime}\
eq\ell_{v}\), \(\ell_{v}\) was either rejected in iteration \(i\) because a lex. smaller label for \(v\) existed in \(Q\) or \(\ell_{v}\) was replaced in \(Q\) by a lex. smaller label for \(v\) (Line 7 of propagate) that was not (\(\operatorname{pos}\) -)dominated by any permanent label at \(v\). Note that multiple such updates to \(v\)'s heap label could have happened until \(\ell_{v}^{\prime}\) is extracted and made permanent.