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.
2003
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]
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/144799
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 2
social impact