Finding all hops k-shortest paths
Gang Cheng, Nirwan Ansari · 2004
In this paper, we introduce and investigate a new problem referred to as the all hops k-shortest paths (AHKP) problem. An efficient solution, the all hops k-shortest paths extended Bellman-Ford (AHKPEB) algorithm, is proposed. Especially, when k = 1, AHKPEB is an optimal comparison-based solution to the all hops optimal path (AHOP) problem in terms of the worst-case computational complexity, i.e., it is impossible to find another comparison-based solution to add-AHOP having the worst-case computational complexity lower than that of AHKPEB.