An O(nm)-Time Network Simplex Algorithm for the Shortest Path Problem

References

• Abrahamson K., Dadoun N., Kirkpatrick D. G., Przytycka T. A simple parallel tree contraction algorithm. J. Algorithms (1989) 10:287–302Crossref, Google Scholar
• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Akgül M. Shortest paths and the simplex method. (1986) . Technical report, Department of Computer Sciences and Operations Research Program, North Carolina State University, Raleigh, NCGoogle Scholar
• Bellman R. On a route problem. Quart. Appl. Math. (1958) 16:87–90Google Scholar
• Cunningham W. A network simplex method. Math. Programming (1976) 11:105–116Crossref, Google Scholar
• Cunningham W. Theoretical properties of the network simplex method. Math. Oper. Res. (1979) 4:196–208Link, Google Scholar
• Dantzig G. B. Discrete-variable extremum principles. Oper. Res. (1957) 5:266–277Link, Google Scholar
• Ford L. R. Network Flow Theory. (1956) . The Rand Corporation Report P-923, Santa Monica, CAGoogle Scholar
• Goldfarb D., Hao J., Kai S. Efficient shortest path simplex algorithms. Oper. Res. (1990a) 38:624–628Link, Google Scholar
• Goldfarb D., Hao J., Kai S. Anti-stalling pivot rules for the network simplex algorithm. Networks (1990b) 20:79–91Crossref, Google Scholar
• Lawler E. L.Combinatorial Optimization: Networks and Matroids (1979) (Holt, Rinehart and Winston New York) Google Scholar
• Minty G. J. A variant on the shortest route problem. Oper. Res. (1958) 6:882Link, Google Scholar
• Moore Z. F. The shortest path through a maze. Proc. Internat. Sympos. Theory Switching, Part II (1957) 285–292Google Scholar
• Orlin J. B. A polynomial time primal network simplex algorithm. Math. Programming-B (1997) 78:109–129Crossref, Google Scholar