# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 2 Review of Related Literature
### KSSP Algorithms  
KSSP applications span diverse domains, including transit routing with scheduled networks [28; 29], autonomous vehicle routing [8], and on-the-fly pathfinding in multi-story buildings [30]. Extensive research has addressed efficient heuristics and algorithms for KSSP in directed graphs, particularly for single-destination scenarios. These approaches leverage the cost function structure or network topology. One of the earliest algorithms for KSSP was proposed by [31] for networks without negative link costs. It involves the repeated application of a single shortest path algorithm where links on the first shortest path are ignored sequentially, one at a time, to find the second shortest path. The minimum of all such paths gives the second shortest path. The \(k\)th simple shortest path is obtained through the recursive application of this procedure. The path deviation-based method of [16] was modified by [32] to address the constrained case of finding only simple paths on networks with positive link costs. An attempt for a labeling method for finding \(k\) simple shortest paths was made by [33] by modifying [PERSON]'s label-setting algorithm [20]. While [PERSON]'s method guarantees pathwise order and avoids loops, it violates conditions (explained in the following section) necessary for exact solutions. Briefly, the conditions are to find paths in a non-decreasing order of path costs and not to restrict the number of labels maintained for any node. By fixing the number of labels to \(k\) for each node and finding the \(i\)th shortest path to each node before the \(i+1\)th shortest path to any node, this label-setting method may not always find the optimal paths. The authors in [34] further illustrate this limitation by proving the theorem \"It may exist a \(k\)th shortest loopless path containing a \(j\)th loopless subpath with \(j>k\)\" using an example network. [PERSON]'s path deviation-based algorithm [5] boasts the best theoretical worst-case complexity \(\left(O(kn(m+n\log n))\right)\) for unrestricted KSSP problems. However, faster algorithms have emerged recently. [PERSON] and [PERSON]'s algorithm [10] targets non-negatively weighted sparse graphs, offering a worst-case complexity of \(O\big{(}k(mn+n^{2}\log(\log n))\big{)}\) through replacement paths. Ref. [35] proposed a similar approach with an optimistic case speedup of \(\theta(n)\), but with potential failures in specific graphs. Ref. [11] improved [PERSON]'s algorithm using a node classification method to reduce the time needed in practice to find new candidate paths on average. Among the fastest practical implementations of KSSP are [PERSON] and [PERSON]'s sidetrack-based algorithm [12] and its proposed improvements by [36], [PERSON]'s T* algorithm for acyclic digraphs [37], and [PERSON] et al. 's deviation-based KSP-LPA* algorithm [13]. More recent research includes [PERSON] et al. 's bi-objective path search approach [38], distributed computing of shortest paths [39], and a graph reduction technique [40]. These algorithms, however, are applied to the single-destination KSSP problem by pruning or partitioning the network into smaller subgraphs. A special case of the multi-destination KSSP has been investigated as a top-k shortest path join problem [41; 42]. Based on graph reduction and bounding procedures, these algorithms deal with specific restricted cases. However, they cannot be used when \(k\) paths are needed for each node in the subset or for all destinations or when the number of paths is not explicitly known a priori. The worst-case complexity can be the same as [PERSON]'s algorithm. Using relatively small subsets (0.01% to 0.15% of nodes in the network) and a very small number of paths (\(k=10\) to 50) on test networks, the authors show one to two orders of magnitude computational time improvement in practice than [PERSON]'s algorithm, but the performance with increasing subset size and number of paths is not evaluated. The KSSP problem has found diverse applications across various domains. [PERSON].