Combining the Shortest Paths and the Bottleneck Paths Problems

Abstract

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(m^2+nc)$ and $O(m^2+mn\log (\frac{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(m^{2}n+nc)$ and $O(m^{2}n+m{n}^2\log (\frac{c}{mn}))$ time bounds. All algorithms presented in this paper are practical for implementation.

Will be presented at ACSC 2014