# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 3 Methodology
### Data Structures for Scalable Performance  
In the heuristic, limiting the number of labels enables some computational enhancements to reduce or avoid some expensive operations from being performed. In Algorithm 1, the temporary labels from all the nodes are maintained together as a single sorted array whose size can be \(O(nk)\). While this structure allows constant time lookups to find the smallest label during node selection, it is inefficient for new label insertion, which occurs frequently during the arc processing step. Therefore, the efficient organization and processing of labels using appropriate data structures could reduce the cost of these operations. Instead of the sorted list, a binary tree structure such as a min heap [48] could be used, which allows constant time lookup for finding the minimum element, and insertions are faster (\(O(\log nk)\)) than the sorted list (\(O(nk)\)). However, finding the maximum label for each node (line 11 of Algorithm 3) requires looking through all the elements, taking \(O(nk)\) time, which could be improved. Therefore, a two-level organization of the temporary labels at the node (local level) and network (global level) is proposed. The smallest temporary label of each node is kept in the global (network) level partition, and the rest of the temporary labels of each node are kept in their corresponding local (node) level partitions, as illustrated in Figure 1. Thus, finding the next permanent label involves only the global heap with \(n\) elements, whereas insertion is performed in the local heap (unless it is the best or first label to a node) with \(k\) elements instead of \(nk\) elements in the single heap. The two-level implementation of the heap data structure also offers the flexibility of using different data structures at the two levels. For efficient label organization and processing, a min heap ([PERSON], 1964) is used in the global structure, which involves only the operation finding the minimum element, whereas the local heap needs both min and max operations. Hence, a min-max heap structure ([PERSON], 1986) is used. In the min heap (binary tree), each parent node has a value no larger than its children, whereas, in the min-max heap, elements at even levels (including the root) have values less than or equal to all their descendants (children, grandchildren, etc.). Conversely, elements at odd levels have values greater than all their descendants. Thus, the minimum element is always at the root, and the maximum element is the maximum of the two elements at the first level. The proposed method of partitioning the node labels is similar to the graph partitioning [45], where different vertices are grouped based on some criteria. However, in the proposed approach, the partitioning is carried out on the node labels based on their cost component rather than the nodes themselves. The pseudocode for the implementation of the heuristic using the proposed data structures is provided in Appendix A and is referred to in the following analysis. This dual heap structure is chosen because the heuristic frequently needs access to the minimum (line 23) and maximum labels (lines 40 and 52) at the local level, and a min-max heap allows both in constant time. The minimum and maximum elements can be read in constant time and updated/removed from the min-max heap in logarithmic time. In each iteration, the heuristic needs access to the minimum label at the global level to make the next permanent  
Figure 1: A graphical representation of the proposed two-level organization for the temporary node labels. label (lines 18 and 19). A min heap allows reading the minimum element in constant time and updating/removing it from the heap in logarithmic time. Following the steps of Proposition 3, the worst-case complexity of the heuristic with data structure improvement (referred to as KSSP_LL_Heap) can be determined as follows. In initialization, insertion into \(T_{global}\) (line 7) takes logarithmic time (\(O(\log n)\)) and creating the label indices (lines 14 and 15) takes \(O(n)\) time.