Forward path search : a new dual coordinate ascent algorithm for shortest paths
Dimitri P. Bertsekas, Decision Systems. · 1990
We propose a new and simple algorithm for finding a shortest path from a single origin to one or more destinations. The algorithm maintains a single path starting at the origin, which is extended or contracted by a single node at each iteration. Simultaneously, at most one dual variable is adjusted at each iteration so as to either improve or maintain the value of a dual function. The algorithm can be extended for the case of multiple origins, and for this case it is well suited for parallel computation.