2013/11/20 by Tong-Wook Shinn, Shinn, Tong-Wook, Tadao Takaoka +1
Computer Science · #Complexity and Algorithms in Graphs #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1311.5081
openalex publication_date 2013/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We combine the well known Shortest Paths (SP) problem and the Bottleneck Paths (BP) problem to introduce a new problem called the Shortest Paths for All Flows (SP-AF) problem that has relevance in real life applications. We first solve the Single Source Shortest Paths for All Flows (SSSP-AF) problem on directed graphs with unit edge costs in O(mn) worst case time bound. We then present two algorithms to solve SSSP-AF on directed graphs with integer edge costs bounded by c in O(m2 + nc) and O(m2 + mnlog((c)/(m))) time bounds. Finally we extend our algorithms for the SSSP-AF problem to solve the All Pairs Shortest Paths for All Flows (APSP-AF) problem in O(m2n + nc) and O(m2n + mn2log((c)/(mn))) time bounds. All algorithms presented in this paper are practical for implementation.