Graph collapsing in shortest path Auction algorithms

In this paper we consider the problem of finding a shortest path from a source node to a fixed target node (SSP) or to all the nodes (SPT) on a directed graph. A family of algorithms which derives from the known auction algorithm is introduced. The key feature of these algorithms is based on topological transformations operated on the graphs that replace an optimal sub-path with a single arc of the same length (graph collapsing concept). The same idea is applied both to the standard auction algorithm and to a modified version of the algorithm. In the last mentioned case a good saving in computation cost is obtained as shown by the reported numerical examples.