Papers › On Constrained and k Shortest Paths
On Constrained and k Shortest Paths
Abderrahim Bendahi, Adrien Fradin
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Finding a shortest path in a graph is one of the most classic problems in algorithmic and graph theory. While we dispose of quite efficient algorithms for this ordinary problem (like the Dijkstra or Bellman-Ford algorithms), some slight variations in the problem statement can quickly lead to computationally hard problems. This article focuses specifically on two of these variants, namely the constrained shortest paths problem and the k shortest paths problem. Both problems are NP-hard, and thus it's not sure we can conceive a polynomial time algorithm (unless P = NP), ours aren't for instance. Moreover, across this article, we provide ILP formulations of these problems in order to give a different point of view to the interested reader. Although we did not try to implement these on modern ILP solvers, it can be an interesting path to explore. We also mention how these algorithms constitute essential ingredients in some of the most important modern applications in the field of data science, such as Isomap, whose main objective is the reduction of dimensionality of high-dimensional datasets.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections