# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 4 Computational Experiments
### Evaluation of Data Structures for Temporary Labels  
The computational performance of the algorithm and the heuristic were evaluated for the single destination KSSP problem. First, a naive implementation was tested where all the temporary labels are maintained in a single level using a sorted list. Then, the proposed two-level organization of temporary labels was tested using four possible combinations of min heap and min-max heap--(i) min heap (global level) and min heap (local level), (ii) min-max heap (global level) and min-max heap (local level), (iii) min heap (global level) and min-max heap (local level), and (iv) min-max heap (global level) and min heap (local level). The average computational time over 50 randomly chosen OD pairs was compared for each network. The experiment was conducted at five different levels of \(k\): 100, 500, 1000, 1500, and 2000. A maximum running time threshold of 30 min was used for each instance, and the test was terminated if the running time for an instance exceeded this threshold. \begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{**Network Density**} & \multicolumn{2}{c}{**Label-Setting Algorithm**} & \multirow{2}{*}{**Current State-of-the-Art**} \\ \cline{2-3} \cline{5-5}  & \(k^{\prime}=\mathbf{\alpha}k\) & \(k^{\prime}=O(n^{2})\) & \\ \hline Dense, \(m=O\big{(}n^{2}\big{)}\) & \(O\big{(}n^{4}\big{)}\) & \(O\big{(}n^{5}\big{)}\) & \(O\big{(}n^{5}\big{)}\) \\ Sparse, \(m=O(n)\) & \(O\big{(}n^{3}\big{)}\) & \(O\big{(}n^{4}\big{)}\) & \(O\big{(}n^{4}\mathrm{log}\,n\big{)}\) \\ \hline \hline \end{tabular} Note: \(\alpha\) is some constant value, and \(k\) is assumed to be \(O(n)\). Yen’s is the state-of-the-art algorithm for dense networks, whereas Gothhif and Lewenstein’s has the best reported complexity on sparse networks with positive costs.  
\end{table} 
Table 2: Comparison of the worst-case time complexities for the multi-destination KSSP problem under different network structures. Table 3 presents the computational results for the naive implementations of Algorithms 1 and 3 using a sorted list. It is important to note that some instances exceeded the 30 min limit, and their running times were capped at the threshold value. Consequently, the average times reported for such cases represent lower bounds rather than exact figures. The results clearly demonstrate the inadequacy of the naive implementations as the algorithms exhibited execution times in the order of several minutes. Figure 2 shows that the best performance is obtained when the node-level labels are handled using a min-max heap, and either a min heap or a min-max heap is used to handle the network-level labels, irrespective of the network size and the number of paths. This makes sense intuitively. When examining nodes during each iteration, the algorithm needs to identify the one with the smallest temporary label. Similarly, when exploring the outgoing arcs from a specific node, the node labels are compared to find the largest one. These operations involve the smallest and largest labels at the network and individual node levels, respectively. The run time difference between a min heap and a min-max heap at the network level is negligible, and both structures efficiently provide access to the minimum element. However, since the min-max heap is unwarranted at the network level, a min heap at the network level and a min-max heap at the node level are recommended. This best-performing data structure combination is used for the rest of the experiments.