Shortest Path Auction Algorithm Without Contractions Using Virtual Source Concept |
| |
Authors: | Raffaele Cerulli Paola Festa Giancarlo Raiconi |
| |
Institution: | (1) Dipartimento di Matematica e Informatica, Università degli Studi di Salerno, via S. Allende, 84081 Baronissi, Salerno, Italy;(2) Dipartimento di Matematica e Applicazioni, Università degli Studi di Napoli FEDERICO II, Compl. Monte S. Angelo, via Cintia, 80126 Napoli, Italy |
| |
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. |
| |
Keywords: | shortest path network optimization auction technique |
本文献已被 SpringerLink 等数据库收录! |
|