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 + n logn + 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∗+n2 logn+n2) algorithm, where m∗ is the number of arcs participating in shortest paths. Notice that m∗ is likely to be small in practice, since m∗ = O(n logn) with high probability for several probability distributions on arc weights.
Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
CANTONE, Domenico;FARO, SIMONE
2014-01-01
Abstract
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 + n logn + 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∗+n2 logn+n2) algorithm, where m∗ is the number of arcs participating in shortest paths. Notice that m∗ is likely to be small in practice, since m∗ = O(n logn) with high probability for several probability distributions on arc weights.File | Dimensione | Formato | |
---|---|---|---|
Fast-shortest-paths-algorithms-in-the-presence-of-few-destinations-of-negative-weight-arcs_2014_Journal-of-Discrete-Algorithms.pdf
solo gestori archivio
Licenza:
Non specificato
Dimensione
275.48 kB
Formato
Adobe PDF
|
275.48 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.