Finding all hops shortest paths

摘要

In this letter, we introduce and investigate a new problem referred to as the All Hops Shortest Paths (AHSP) problem. The AHSP problem involves selecting, for all hop counts, the shortest paths from a given source to any other node in a network. We derive a tight lower bound on the worst-case computational complexities of the optimal comparison-based solutions to AHSP.