Single Source Shortest Paths for All Flows with Integer Costs

摘要

We consider a shortest path problem for a directed graph with edges labeled with a cost and a capacity. The problem is to push an unsplittable flow $f$ from a specified source to all other vertices with the minimum cost for all f values. Let G = (V, E) with |V| = n and |E| = m. If there are t different capacity values, we can solve the single source shortest path problem t times for all f in O(tm + tn log n) time, which is O(m^2) when t = m. We improve this time to O(min{t, cn}m + cn^2), which is less than O(cmn) if edge costs are non-negative integers bounded by c. Our algorithm performs better for denser graphs.