# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 3 Methodology
### Label-Setting KSSP Algorithm
```
Input: The network instance \(G(N,A)\) and origin \(s\) Output: The set of \(k\) simple shortest path labels \(P\)
1 // Create a label \(d_{s}^{1}\) corresponding to the first path to the origin \(s\)
2 \(d_{s,1}^{1}\gets s\)
3 \(d_{s,2}^{1}\gets NULL\)
4 \(d_{s,3}^{1}\gets 0\)
5 // Create a temporary set \(T\) and move \(d_{s}^{1}\) into \(T\)
6 \(T\leftarrow\emptyset\)
7 \(T\gets T\cup\{d_{s}^{1}\}\)
8 // Create an empty permanent set \(P\)
9 \(P\leftarrow\emptyset\)
10 // Initialize the label index and permanent label index for each node
11 \(l_{s}\gets 1\)
12 \(l_{i}\gets 0,\forall\ i\in N\setminus\{s\}\)
13 \(p_{i}\gets 0,\forall\ i\in N\)
14 Repeat
15 // Pick the minimum cost label \(d_{u}^{p_{u}+1}\) from \(T\) and move it to \(P\), making it permanent

\(d_{u}^{p_{u}+1}\leftarrow\min\limits_{d_{i}^{j}\in T}\left(d_{i}^{j}\right)\)
16 // Since \(p_{u}\) labels are permanent for node \(u\), \(p_{u}+1\) is the next smallest temporary label index of \(u\)
17 \(T\gets T\setminus\{d_{u}^{p_{u}+1}\}\)
18 \(P\gets P\cup\{d_{u}^{p_{u}+1}\}\)
19 // Increment the permanent label index of node \(u\)
20 \(p_{u}\gets p_{u}+1\)
21 For each node \(v\) adjacent to \(u\)do
22 IfCycleCheck(\(s\), \(u\), \(p_{u}\), \(v\)) is FALSE then // \(v\) is not on the path corresponding to \(p_{u}\)
23 // The path corresponding to the permanent label index \(p_{u}\) extended with the arc \((u,v)\) is acyclic
24 // Create a new label and place it in the sorted order of path cost among the existing temporary labels of \(v\)
25 // Create a new label \(d_{v}^{j}\)
26 \(d_{v,3}^{j}\leftarrow\left(d_{u,3}^{p_{u}}+C_{u,v}\right)\)
27 \(d_{v,2}^{j}\gets p_{u}\)
28 \(d_{v,1}^{j}\gets u\)
29 \(T\gets T\cup\{d_{v}^{j}\}\)
30 // Increment the label index of node \(v\)
31 \(l_{v}\gets l_{v}+1\)
32
33 Until \(T\) is \(\emptyset\) or \(p_{i}\geq k\)\(\forall i\in N\setminus\{s\}\) // No more temporary labels to process or at least \(k\) permanent labels to every destination are found
```  
**Algorithm 1**Exact_KSSP\((G(N,A),s)\to P\)  
Next, we prove Hypothesis 2, provided Hypothesis 1 holds. Let us assume that Hypothesis 2 is true before the label \(d_{u}^{p_{u}+1}\) from \(T\) is moved to \(P\). We need to prove that it holds after moving the label (lines 16-17) and arc processing update (lines 22-26). Consider an arbitrary label in \(T\), say \(d_{i,1}^{p_{i}+1}\). To show: \(d_{i,3}^{p_{i}+1}\) is the optimal \(p_{i+1}\)th distance from \(s\) to \(i\) among the labels in \(P\cup d_{u}^{p_{i}+1}\). Before the update, \(d_{i}^{p_{i}+1}\) is the shortest \(p_{i+1}\)th label to \(i\) among paths made up of those labels in \(P\) (induction hypothesis). The \(p_{i+1}\)th optimal path from \(s\) to \(i\) made up of labels in \(P\cup d_{u}^{p_{u}+1}\) either contains the link \((u,\ i)\) or does not contain the link \((u,\ i)\). If it does not contain the link \((u,\ i)\), then the label \(d_{i}^{p_{i}+1}\) satisfies Hypothesis 2. If the \(p_{i+1}\)th optimal path from \(s\) to \(i\) made up of labels in \(P\cup d_{u}^{p_{i}+1}\) contains the link \((u,\ i)\), then the arc processing update implies that a new label \(d_{i,3}^{j}=d_{u}^{p_{u}+1}+C_{u,\ i}<d_{i,3}^{p_{i}+1}\) is created and inserted in the sorted order so that \(j=p_{i+1}\). Thus, the arc processing update ensures that Hypothesis 2 is satisfied for the \(d_{i}^{p_{i}+1}\)th label in \(T\). The \(d_{i}^{p_{i}+1}\)th label is arbitrarily chosen. So, the hypothesis is true for all labels in \(T\). Therefore, by making the smallest label in \(T\) permanent, followed by the arc processing updates in each iteration, the label-setting algorithm produces the optimal solution. \(\square\)  
Remark: The proposed label-setting algorithm will enumerate simple paths from the origin in a non-decreasing order of path cost. Proposition 2: The label-setting algorithm terminates in a finite number of iterations. \({}_{\blacksquare}\)  
Proof: The number of nodes in the network and the number of simple paths from origin \(s\) to any node are finite.