# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## Appendix A  
In each iteration, execution of the cycle check procedure takes at most \(O(n)\) time. The cycle check in line 21 of Algorithm 1 is performed by backtracking the nodes in a path. Since the maximum number of nodes in a simple path cannot exceed n without a node getting repeated, the loop in the cycle check procedure repeats for at most \(O(n)\) iterations. \(\square\)  
**Remark A1**. : _All proposed variants of the label-setting algorithm also terminate in a finite number of iterations since their termination condition may lead to an early stopping of the algorithm._  
Detailed proof of Proposition 2.: The termination of Algorithm 1 in line 29 depends on the size of the temporary label set (\(|T|\)). The algorithm starts with a single temporary label (\(|T|=1\)) (line 7) and in each iteration, at most \(n\) labels can be added to \(T\) if new simple paths are found from \(s\) to each node \(v\) in the network (lines 20-28). The number of nodes in the network and the number of simple paths from origin \(s\) to any node are finite. Let the maximum number of simple paths to any node be \(k^{\prime}\). Therefore, the maximum size of the set \(T\) is also finite (\(|T|\leq nk^{\prime}\)). Since one temporary label is removed from \(T\) and made permanent (i.e., the label will not enter into \(T\) again) in each iteration (lines 16-17), the set \(T\) becomes empty in a finite number of iterations, and the algorithm terminates. \(\square\)  
Detailed worst-case time complexity analysis for Algorithm 1  
Termination occurs when one of two conditions are met--\(T\) becomes empty or \(k\) permanent labels are found for all the nodes. The worst case is when all temporary labels must be examined (for example, the longest path from the origin is the \(k\)th shortest path to some node), which is analyzed here. The algorithm can be broken down into four major parts and analyzed separately in detail below. Initialization: Lines 1-11 are constant time operations and can be completed in \(O(1)\) time. Lines 12-13 take \(O(n)\) time in total to initialize the label indices for the nodes in the network. Node selection: Let us assume that \(T\) is naively implemented as a sorted list. The minimum cost label in line 15 can be found in \(O(1)\) time. In the worst case, the maximum number of times line 15 is executed equals the maximum number of temporary labels created. The algorithm can enumerate all the simple paths from the origin before finding the required number of simple paths to the destination or the set of destinations of interest. From Proposition 2, the maximum number of temporary labels created is \(nk^{\prime}\), and the total time complexity of line 15 is \(O(nk^{\prime})\). Moving the minimum cost label from \(T\) to \(P\) and incrementing the permanent label index (lines 16-19) finishes in \(O(1)\) time. Arc processing: For a node \(u\), the loop in line 20 repeats \(outdegree(u)\) times. When one permanent label is found to each node, the number of repetitions is \(\Sigma_{i\in N}outdegree(i)=m\). For \(O(k^{\prime})\) paths found in the worst case, the loop executes \(O(mk^{\prime})\) times. The cycle check in line 21 takes \(O(n)\) time, as established in the lemma earlier. A temporary label can be created in \(O(1)\) time (lines 22-25). Since \(T\) is maintained as a sorted list, insertion of a new label into \(T\) takes \(O(nk^{\prime})\) (the maximum size of \(T\)) time (line 26). The total complexity of the loop from lines 20-28 is \(O(mk^{\prime}(n+nk^{\prime}))\). Termination check: the check for the termination conditions in line 29 takes \(O(n)\) time.