Browsing the wikipedia I got to this page where it is said:
Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one path.
The same statement is somewhat repeated in the hall of fame of algorithms:
To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path
Then, the Wikipedia (i.e., the first link, not the second) goes into proving how it is possible to extend Dijkstra's algorithm to solve the loopy variant (i.e., where non-simple paths are allowed). The extension is absolutely simple as it simply consists of allowing each node to be expanded up to $k$ times, with $k$ the number of paths to find to the goal state. This idea, indeed, was generalized by Rina Dechter to consider heuristics as well:
- Rina Decther, Natalia Flerova and Radu Marinescu. Search algorithms for $m$ best solutions for Graphical Models. AAAI 20, pp. 1895--1901
- Natalia Flerova, Radu Marinescu and Rina Dechter. Search algorithms for the $m$ best solutions in Graphical Models. Journal of Artificial Intelligence Research (55) 2016, pp. 889--952.
However, I never heard of any extension of Bellman-Ford for solving neither the loopy nor the loopless variants of the $k$ shortest path routing problem. Moreover, I'm not aware of any algorithm that can solve this problem in the presence of negative edge costs.
The only variant I can think of for extending Bellman-Ford is observing that upon termination the cost of the optimal path of one designated vertex to all the other vertices $v\in V$, $d_v$, is known so that one could run sort of a Recursive Best-First Search to enumerate all paths. Maybe is this what the authors of those pages mean?
Thus, my questions are:
- What is the way to extend Bellman-Ford to solve the $k$ shortest path routing problem?
- Are there any algorithms out there for solving the $k$ shortest path routing problem with negative edge costs (provided there are no negative cycles)? Note that neither Eppstein's nor Yen's algorithm can deal with negative edge costs.
This is all I know about the subject and please note that my questions are a result of my ignorance so that I would be very grateful if any answer is provided or any link I could follow.