# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 3 Methodology
### Label-Setting KSSP Algorithm  
In the label-setting algorithm, a node's label \(d^{k}_{i}\) represents the \(k\)th simple shortest path from a pre-specified origin node \(s\) to node \(i\) and comprises three components: the predecessor node (\(d^{k}_{i,1}\)), predecessor node's label index (\(d^{k}_{i,2}\)), and cost of the path (\(d^{k}_{i,3}\)). At any iteration of the algorithm, each node label belongs to one of two sets, namely, \(P\) and \(T\). \(P\) is a set of permanent labels whose components are guaranteed not to change subsequently. \(T\) is a set of temporary labels where one or more of a label's components may change in further iterations of the algorithm. Let \(l_{i}\) be an index for the number of labels created for node \(i\) and \(p_{i}\) be the number of permanent labels for node \(i\). First, the algorithm, proof of correctness and complexity analysis for the KSSP-OA problem are presented, and then the solution procedure for the rest of the variants is provided. In the proposed labeling approach for finding shortest paths, [PERSON]'s principle of optimality [46], also known as triangle inequality, is preserved by iteratively updating the labels that violate it. The algorithm begins with a single temporary label representing a trivial path to reach the origin \(s\) (from itself with zero cost). In each iteration, the temporary label with the least cost among all nodes is made permanent (the rationale is discussed later). The adjacent nodes are then explored, creating new temporary labels (i.e., new paths to those adjacent nodes), provided they are acyclic. The algorithm terminates when all the created labels are made permanent, i.e., all simple paths from \(s\) in the network are enumerated, or \(k\) best simple paths are found and permanently labeled for each destination. The pseudocode for the label-setting KSSP algorithm is given below as Algorithm 1. The cycle check in line 21 of Algorithm 1 follows the procedure in Algorithm 2 below. **Proposition 1**: _In the optimal KSSP solution, for any node, the minimum number of labels created is at least \(k\), and in the worst case, the maximum number of labels created is \(O((n-2)! )\)._  
Assuming that at least \(k\) simple paths exist from the origin \(s\) to an arbitrary node \(p\), and since one label is required to represent one distinct path, it is evident that the minimum number of labels to be created for \(p\) is \(k\). However, in some cases, the first \(k\) labels may not be sufficient. We prove this claim by contradiction. Let us assume that limiting the number of labels created for each node \(i\) (\(l_{i}\)) to \(k\) is sufficient to ensure the correctness of the KSSP solution. Consider two arbitrary nodes, \(p\) and \(q\), in a network with non-negative link costs where KSSP from origin \(s\) is to be found. Suppose the \(k\)th simple shortest path to \(q\) is as follows. \[d^{1}_{s}\rightarrow\cdots\to d^{r}_{p}\rightarrow\cdots\to d^{k}_{q^{ \prime}}(r>k)\]  
The above path to \(q\) comprises the \(r\)th simple shortest path to \(p\) as a subpath such that \(r>k\). This is possible because the subpath optimality does not hold for the KSSP problem. In order for \(d_{q}^{k}\) to be found, \(d_{p}^{r}\) should have been found and made permanent earlier. So, when \(d_{q}^{k}\) is made permanent (i.e., \(p_{q}=k\)), the following should hold:  
\[p_{p}\geq r\]  
However, since \(l_{i}\) is restricted to \(k<r\) for each node \(i\), \(p_{p}<r\), in which case, \(d_{q}^{k}\) is not guaranteed to be optimal. This contradicts our assumption that limiting \(l_{i}\) to \(k\)\(\forall i\) will ensure the correctness of the solution. As \(p\) and \(q\) are arbitrarily chosen, we must allow for more than \(k\) labels per node to accommodate scenarios where \(j>k\) subpaths are necessary for finding the \(k\) optimal simple paths to a node. Lastly, we show that in the worst case, the maximum number of labels that can be created for a node is bounded by \(O((n-2)!)\).