کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430858 | 688215 | 2014 | 14 صفحه PDF | دانلود رایگان |
In this paper we present hybrid algorithms for the single-source shortest-paths (SSSP) and for the all-pairs shortest-paths (APSP) problems, which are asymptotically fast when run on graphs with few destinations of negative-weight arcs. Plainly, the case of graphs with few sources of negative-weight arcs can be handled as well, using reverse graphs. With a directed graph with n nodes and m arcs, our algorithm for the SSSP problem has an O(ℓ(m+nlogn+ℓ2))-time complexity, where ℓ is the number of destinations of negative-weight arcs in the graph. In the case of the APSP problem, we propose an O(nm⁎+n2logn+ℓn2) algorithm, where m⁎m⁎ is the number of arcs participating in shortest paths. Notice that m⁎m⁎ is likely to be small in practice, since m⁎=O(nlogn) with high probability for several probability distributions on arc weights.
Journal: Journal of Discrete Algorithms - Volume 24, January 2014, Pages 12–25