snippetMinor
How to extend Bellman-Ford to solve the $k$ shortest path routing?
Viewed 0 times
extendbellmanthepathshortestfordsolvehowrouting
Problem
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:
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:
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$ s
Solution
It seems that we can use the following generalization of Bellman-Ford. Let's store a set $Pt_{v}$ of $k$ numbers for each vertex $v$ of graph $G$ which initially are all equal to $+\infty$. The only exception is a vertex $s$ (the vertex from which all paths are calculated). Its set $Pt_{s}$ should be initialized to a single value of $0$ and $k-1$ values of $+\infty$.
Now let's run $k \cdot |V|$ iterations of relaxations (instead of $|V| - 1$ iterations like in usual Bellman-Ford) and try to maintain the following invariant. After $i$-s iteration for each vertex $v$ the $j$-s least number from $Pt_{v}$ should be not greater than the length of the $j$-s shortest path from $s$ to $v$ containing not more than $i$ edges. This invariant will be maintained by means of proper edge relaxations. For each $(u, v)$ edge relaxation we should assign $Pt_{v}$ to a set of $k$ least numbers from a set $Pt_{v} \cup \{x + weight(u, v)|x\in Pt_{u}\}$.
So after all $|V|-1$ iterations each set $Pt_{v}$ will contain $k$ shortest paths from $s$ to $v$. The proof of correctness for this algorithm should be literally the same as for usual Bellman-Ford.
This is a loopy algorithm. Its time complexity is $O(|V|\cdot|E|\cdot k^2)$ (because single edge relaxation can be done in $O(k)$ time using a selection algorithm).
Now let's run $k \cdot |V|$ iterations of relaxations (instead of $|V| - 1$ iterations like in usual Bellman-Ford) and try to maintain the following invariant. After $i$-s iteration for each vertex $v$ the $j$-s least number from $Pt_{v}$ should be not greater than the length of the $j$-s shortest path from $s$ to $v$ containing not more than $i$ edges. This invariant will be maintained by means of proper edge relaxations. For each $(u, v)$ edge relaxation we should assign $Pt_{v}$ to a set of $k$ least numbers from a set $Pt_{v} \cup \{x + weight(u, v)|x\in Pt_{u}\}$.
So after all $|V|-1$ iterations each set $Pt_{v}$ will contain $k$ shortest paths from $s$ to $v$. The proof of correctness for this algorithm should be literally the same as for usual Bellman-Ford.
This is a loopy algorithm. Its time complexity is $O(|V|\cdot|E|\cdot k^2)$ (because single edge relaxation can be done in $O(k)$ time using a selection algorithm).
Context
StackExchange Computer Science Q#120461, answer score: 3
Revisions (0)
No revisions yet.