2026-07-22T05:22:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5461 2024-03-06T10:29:49Z ddc:004 open_access

Single Source Shortest Paths for All Flows with Integer Costs Takaoka, Tadao information sharing shortest path problem for all flows priority queue limited edge cost transportation 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tadao Takaoka 2015 Is Part Of OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2015.56 urn:nbn:de:0030-drops-54611 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.56 eng https://creativecommons.org/licenses/by/3.0/legalcode