Shortest path auction algorithm without contractions using virtual source concept

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.