Algebraic Theory on Shortest Paths for All Flows

摘要

As a mathematical model for the passenger routing problem for ticketing in a railway network, we consider a shortest path problem for a directed graph with edges labeled with a cost and a capacity. The problem is to push flow f from a specified source to all other vertices with the minimum cost for all f values. If there are t different capacity values, we can solve the single source shortest path problem for all f t times in O(tm + tn log n)=O(m~2) time when t = m. We improve this time to O(cmn) if edge costs are non-negative integers bounded by c.