# Combining the Shortest Paths and the Bottleneck Paths Problems

Preprint · Tong-Wook Shinn, Tadao Takaoka

- Archive id: arxiv:1311.5081
- Published: 2013-11-20
- arXiv: https://arxiv.org/abs/1311.5081
- Citations: 6
- Source URL: https://arxiv.org/abs/1311.5081
- PDF: https://arxiv.org/pdf/1311.5081
- Provenance: arxiv

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

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.