Abstract
The Shortest Path Problem with Forbidden Paths (SPPFP) is a variant of the original shortest path problem, where the constraints come from a set of forbidden arc sequences that cannot be part of any feasible solution. Though this problem is addressed in the academic literature and has numerous applications, there are no open-source implementations of algorithms that solve it. This article proposes “rsppfp”, an R package that offers functionalities that solve the SPPFP by transforming it into the traditional shortest path problem. Its main strengths are its parallel processing capability, and it is high compatibility with packages for other network research. In this paper, we describe the design and functionality of “rsppfp”, report an evaluation made with different graph structures, and provide guidelines and examples for its use.
Acknowledgements
The authors gratefully acknowledge the financial support for the work presented in this article to Universidad Tecnológica Nacional (UTN), Argentina through PID EIUTIFE0003974TC. Also, the authors appreciatively recognise the extraordinary efforts of the anonymous reviewers for their suggestions for improving the read of the article and the quality of the code.
Citation
@article{Vidoni2019,
title = {“rsppfp”: An R package for the shortest path problem with forbidden paths},
journal = {SoftwareX},
volume = {9},
pages = {265-270},
year = {2019},
issn = {2352-7110},
doi = {https://doi.org/10.1016/j.softx.2019.03.004},
url = {https://www.sciencedirect.com/science/article/pii/S2352711018300955},
author = {Melina Vidoni and Aldo Vecchietti},
keywords = {R package, Shortest path, Forbidden paths, Network flows},
}
Venue Impact
The following is the venue impact, according to Scimago Journal Ranking: