A Successive Shortest Path Algorithm for The Assignment Problem
Michael Lawrence Engquist · INFOR Information Systems and Operational Research · 1982
In this paper a new successive shortest path (SSP) algorithm for solving the assignment problem is introduced. A computer implementation of this algorithm has been developed and a discussion of the details of this implementation is provided. Computational resultsare presented that show this implementation of SSP to be substantially more efficient thanseveral recently developed codes, including the best primal simplex code. Also, some new theoretical results are presented which are useful in the implementation of SSP, and itisshown that tlie algorithm has a computational bound of 0(n3),where n is the number of origins.