# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 3 Methodology
### Data Structures for Scalable Performance
So, the initialization takes \(O(n)\) time in total. In node selection, the minimum cost label can be found in constant time (root element of \(T_{global}\)). Moving the minimum from \(T_{global}\) to \(P\) (lines 18 and 19) happens in logarithmic time (\(O(\log n)\)). Removal from the min-max heap (line 23) and insertion into the min heap (line 24) happen in a logarithmic time of \(O(\log k)\) and \(O(\log n)\), respectively. Since node selection happens at most \(nk\) times, the total complexity of this step is \(O(nk(\log k+\log n))=O(nk\log kn)\). The bottleneck in the arc processing loop is the branch from lines 40 to 52. Here, the cycle check (line 41) takes \(O(n)\) time. The removal and insertion operations for the min heap (lines 47 and 48) take \(O(\log n)\) time each. Insertion into the min-max heap (lines 49 and 51) takes \(O(\log k)\) time. Removal from the min-max heap (line 52) also takes \(O(\log k)\) time. As the maximum number of iterations of the loop is \(mk\), the total complexity of arc processing is \(O(mk(n+\log k+\log n))=O(mk(n+\log k))\). The termination check takes \(O(n)\) time. The overall complexity of the heuristic is \(O(n+nk(\log kn)+mk(n+\log k))=O(mk(n+\log k))\). Next, the worst-case time complexities of the proposed and state-of-the-art algorithms for the multi-destination KSSP problem under different network structures are compared. The current state-of-the-art worst-case time complexity achieved through \(n\) repeated applications of [PERSON]'s KSSP algorithm is \(O\big{(}kn^{2}(m+n\log n)\big{)}\) and [PERSON]'s algorithm is \(O\big{(}kn^{2}(m+n\log(\log n))\big{)}\). For dense networks where \(k\) is \(O(n)\), both have a complexity of \(O\big{(}n^{5}\big{)}\), whereas for sparse networks with non-negative costs, the latter is faster (\(O\big{(}n^{4}\log(\log n))\)). The worst-case complexity of the exact Algorithm 1 with the proposed two-level label organization is \(O(mk^{\prime}(n+\log k^{\prime}))\), where \(k^{\prime}\geq k\) denotes the maximum number of labels created by the algorithm for any node. As the maximum number of labels created for a node in Algorithm 1, in the worst case, is \(k^{\prime}=O(2^{n})\), the worst-case complexity of the exact algorithm is pseudo-polynomial. Four special cases which are more likely to arise in practice are considered: (1) dense networks with \(k\prime=O(k)\), (2) dense networks with \(k\prime=O\big{(}n^{2}\big{)}\), (3) sparse networks with \(k\prime=O\big{(}n^{2}\big{)}\), and (4) sparse networks with \(k\prime=O\big{(}n^{2}\big{)}\). By using the fact that \(m=O(n)\) for sparse networks and \(m=O\big{(}n^{2}\big{)}\) in dense networks and assuming the number of paths of interest is of the same order of magnitude as the number of nodes (\(k=O(n)\)), in case 1, the complexity of Algorithm 1 (exact label-setting algorithm) reduces to \(O\big{(}n^{4}\big{)}\), which is better than the popular [PERSON]'s algorithm. In case 2, the complexity is \(O\big{(}n^{5}\big{)}\), which is the same as the state-of-the-art algorithm. In case 3, the proposed algorithm has a complexity of O(n\({}^{3}\)), which is faster than the existing algorithm by an order of magnitude. In case 4, the algorithm has a complexity of O(n\({}^{4}\)), which is faster than the state-of-the-art algorithm by \(O(\log(\log n))\). Table 2 summarizes these time complexities under different network structures and the number of labels \(k^{\prime}\). Thus, it is clear that the proposed label-setting algorithm is theoretically superior in sparse networks and comparable to [PERSON]'s algorithm whenever the number of labels created \(k^{\prime}\) is bounded from above by \(O\big{(}n^{2}\big{)}\) and the number of paths \(k\) of interest is \(O(n)\). The empirical experiments described in the next section using many real-world networks, which are usually sparse, show that this condition typically holds in practice. Besides the computational performance, the results also examine the trade-off in solution quality between the exact algorithm and the heuristic.