# Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects +
## 2 Dynamic Shortest Path
### Representative Algorithms for DSP  
This section presents some of the representative algorithms for DSP problems in the literature, pointing out at the end their limitation if applied to solve an MODSP problem. Figure 1: Shortest path graph example with vertices named by the letters \(s,a,b,c\), and \(d\) being \(s\) the source vertex and d the destination vertex. The number over the edge represents the edge traverse cost between two vertices. The reader interested in the DSP state-of-the-art algorithms is referred to access the work of [PERSON] [13] to be redirected to those works. Moreover, it is possible to find a literature review on traffic safety in [PERSON] et al. [14]. Algorithms addressed to solve the DSP problems in the literature can be exact or approximate. While the exact algorithms offer genuine responses regarding the optimal routes, the approximative algorithms propose solutions within a bound from the optimal [15]. The choice of which type of dynamic algorithm to use can be guided by the update and query time, which measure the efficiency of dynamic algorithms. The exact algorithms present a polynomial amortized time cost for updates on the graph \(\tilde{O}(n^{k})\) with \(k\approx 2\), where \(n\) is the number of vertices [16]. The disruptive work for the fully dynamic APSP on directed graphs with non-negative weights was introduced by [PERSON] and [PERSON] [16]. Their work realized update operations in an amortized complexity of \(O(n^{2}\log^{3}n)\) and each query in \(O(1)\) worst-case time. Moreover, the local shortest path approach and the data structure adopted by [PERSON] and [PERSON] served as a base motivating more researchers to exploit the exact fully dynamic APSP algorithms. This was the case for [PERSON] [17], who made improvements on the [PERSON] and [PERSON] approach to the use of negative weights. [PERSON]'s work reached a \(O(n^{2}(\log n+\log^{2}(m/n)))\) amortized update time, where \(m\) is the number of edges, maintaining the constant query time. Approximate algorithms, despite not guaranteeing an optimal response, present responses within a bound of the optimal (\((1+\epsilon)\)-approximate [18]). Those algorithms have an amortized update time cost that is almost linear [19]. [PERSON] and [PERSON] [20] contributed to developing approximate algorithms for incremental and decremental SSSPs, which find the shortest path with the optimal solution proximity of \((1+\epsilon)\) in an amortized complexity of \(\tilde{O}(n)\). They also contributed with a full APSP that solves the updates with a time complexity of \(\tilde{O}(mn/t)\), with \((1\leq t\leq\sqrt{m})\), a query response time in \(O(t)\). [PERSON] and [PERSON] [18] also presented a fully APSP approximate algorithm using the fast matrix technique to improve the worst-case update time to \(\tilde{O}(n^{2.045}/\epsilon^{2})\); their work considered only directed graphs with positive weights at the edges. As a counterpart, the [PERSON] and Nanongkai algorithm maintains only the distances and cannot report the corresponding paths. In addition to those DSP algorithms, traffic networks are an important field in developing algorithms for the DSP problem, answering real-time traffic changes. Aiming to treat conditions such as accidents, traffic jams, and bad weather in real-time, [PERSON] et al. [21] proposed a framework based on dynamic programming for hybrid routing policies in transit networks. [PERSON] and [PERSON] [22] developed an algorithm for the DSP problem considering the graph in continuous time to find the best route in real-time. Moreover, [PERSON] and [PERSON] [23] proposed a way to find the shortest paths in traffic networks subject to dynamic and stochastic changes using a heuristic algorithm based on the K-shortest path. The main drawback of DSP algorithms is the space complexity \(O(mn)\) for storing the paths generated [16]. This disadvantage is necessary since the stored paths are the core that allows recalculating only the affected part by the update and avoids recomputing all paths from scratch.