Variations on the bottleneck paths problem

We extend the well known bottleneck paths problem in two directions for directed graphs with unit edge costs and positive real edge capacities. Firstly we narrow the problem domain and compute the bottleneck of the entire network in O(mlog⁡n) time, where m and n are the number of edges and vertices in the graph, respectively. Secondly we enlarge the domain and compute the shortest paths for all possible bottleneck amounts. We call this problem the Shortest Paths for All Flows (SP-AF) problem. We present a combinatorial algorithm to solve the Single Source SP-AF problem in O(mn) worst case time, followed by an algorithm to solve the All Pairs SP-AF problem in O(tn(ω+9)/4) time, where t is the number of distinct edge capacities and O(nω) is the time taken to multiply two n-by-n matrices over a ring.