Strongly polynomial Auction algorithms for shortest path

An Auction algorithm for shortest paths was recently proposed by Bertsekas. Under the assumption that each cycle of the graph has a positive length, that the forward star of each node is not empty and that the input data are integer, a shortest path tree is returned in psuedopolynomial time. In this work, the authors propose two new versions of the Bertsekas algorithm, which generalize the Auction approach for shortest paths. In addition, they are strongly polynomial. In fact, the first algorithm runs in O(m²) time and the second one in O(mn), where m and n are the number of the edges and the number of the nodes of the graph, respectively.