# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 6 Conclusions  
This study proposes a novel label-setting framework for solving the multi-destination KSSP problem and its variants in directed graphs with non-negative edge weights. The proposed labeling framework obviates the need to repeatedly solve the KSSP problem for each destination as is necessary in path deviation algorithms (such as Yen's), resulting in a significant speedup of the algorithm. An exact algorithm, which is pseudo-polynomial, and a practically efficient heuristic based on bounded labels and a two-level heap data structure are implemented and evaluated theoretically and using computational experiments on several real-world networks.  
An efficient heuristic is developed and implemented by limiting the number of labels for each node to \(k\) and designing a two-level heap data structure to store temporary labels. The proposed KSSP_LL_Heap heuristic has a complexity of \(O(mk(n+\log k))\), which is polynomial in \(k\) and network size, and offers significant computational benefits over state-of-the-art algorithms with a marginal degradation of solution quality. As a result, the worst-case complexity of the heuristic is significantly faster in both sparse and dense networks than existing state-of-the-art algorithms.  
Computational experiments on many real-world networks corroborate the findings from the above theoretical complexity analysis. The proposed heuristic provides significant computational speedups from 29 to 1416 times over the state-of-the-art algorithms in real-world networks of varying sizes and \(k\) values with negligible loss in accuracy (at most 0.167%). Finally, a practical application of the proposed method is illustrated to determine the gravity of an edge (relative structural importance) in a network.  
The multi-destination KSSP offers a robust framework for tackling several applications in the future, including the following: (i) a KSSP-OM approach, incorporating real-time crowding data, can dynamically be used to re-route passengers departing from mass gathering events through less congested alternative paths, minimizing travel time and improving passenger experience and (ii) a CCSSP-OA formulation can be applied to assess the number of travel options available from a specific location within a limited time budget, aiding in the evaluation and promotion of more accessible public transit systems. Extensions to multi-criterion and time-dependent versions are challenging areas for further research.  
Conceptualization, S.V.U., K.K.S., P.K., and B.R.C.; Methodology, S.V.U., K.K.S., P.K., and B.R.C.; Investigation, S.V.U. and K.K.S.; Formal analysis, S.V.U. and K.K.S.; Writing--original draft, S.V.U., K.K.S., P.K., and B.R.C.; Writing--review and editing, S.V.U., K.K.S., P.K., and B.R.C.; Software, S.V.U.; Funding acquisition, S.V.U. and K.K.S. All authors have read and agreed to the published version of the manuscript.  
This work was partly supported by the Science and Engineering Research Board, Department of Science & Technology, Government of India [grant number IMP/2018/001850] and the Prime Minister's Research Fellows (PMRF) scheme, Ministry of Education, Government of India.  
The data presented in this study are openly available in GitHub at [[https://github.com/bstabler/TransportationNetworks](https://github.com/bstabler/TransportationNetworks)]([https://github.com/bstabler/TransportationNetworks](https://github.com/bstabler/TransportationNetworks)) (accessed on 28 September 2019).  
The authors declare no conflict of interest.