Experimental effectiveness of Auction Algorithms for the determination of shortest paths

Recently many Auction Algorithms have been proposed to find shortest paths in directed graphs. The Auction method updates, at each iteration, a path outgoing from the root and the node potentials by means of extension and contraction operations; moreover the graph is progressively reduced by deleting arcs and by blocking nodes. The aim of the paper is to analyze the performance of various versions of the Auction algorithms; Two sub-families of algorithms are taken into consideration: (a) the Auction