In this paper, the problem of finding a shortest path tree rooted at a given source node on a directed graph (SPT) is considered. A new efficient algorithm based on a primal-dual approach is presented, which improves both the convergence and the complexity of the best known auction-like algorithm. It uses the virtual source (VS) concept based on the following consideration: when a node i is visited for the first time by any algorithm which preserves verified the dual admissibility conditions, then the shortest path (SP) from the source node to i is found. Therefore, the SP from the source to the remaining nodes may be computed by considering i as a virtual source. We propose a very efficient implementation of an auction-like algorithm that uses this concept and enables us to obtain a computational cost of O(n^2), where n is the number of nodes. Numerical experimentsare reported showing that the new method outdoes previously proposed auction-like algorithms and is highly competitive with other state-of-art SP approaches.
Shortest path auction algorithm without contractions using virtual source concept / Festa, Paola; R., Cerulli; G., Raiconi. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - 26:2(2003), pp. 191-208. [10.1023/A:1025750631443]
Shortest path auction algorithm without contractions using virtual source concept
FESTA, PAOLA;
2003
Abstract
In this paper, the problem of finding a shortest path tree rooted at a given source node on a directed graph (SPT) is considered. A new efficient algorithm based on a primal-dual approach is presented, which improves both the convergence and the complexity of the best known auction-like algorithm. It uses the virtual source (VS) concept based on the following consideration: when a node i is visited for the first time by any algorithm which preserves verified the dual admissibility conditions, then the shortest path (SP) from the source node to i is found. Therefore, the SP from the source to the remaining nodes may be computed by considering i as a virtual source. We propose a very efficient implementation of an auction-like algorithm that uses this concept and enables us to obtain a computational cost of O(n^2), where n is the number of nodes. Numerical experimentsare reported showing that the new method outdoes previously proposed auction-like algorithms and is highly competitive with other state-of-art SP approaches.File | Dimensione | Formato | |
---|---|---|---|
a7_vvsa.pdf
non disponibili
Tipologia:
Documento in Post-print
Licenza:
Accesso privato/ristretto
Dimensione
118.12 kB
Formato
Adobe PDF
|
118.12 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.