A Multiple Pairs Shortest Path Algorithm

References

• Aho A. V., Hopcroft J. E., Ullman J. D.The Design and Analysis of Computer Algorithms (1974) (Addison-Wesley, Reading, MA) 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
• Ahuja R. K., Mehlhorn K., Orlin J. B., Tarjan R. E. Faster algorithms for the shortest path problem. J. ACM (1990) 37(2):213–223Crossref, Google Scholar
• Backhouse R. C., Carré B. A. Regular algebra applied to path finding problems. J. Inst. Math. Appl. (1975) 15(2):161–186Crossref, Google Scholar
• Barnhart C., Johnson E. L., Hane C., Sigismondi G. An alternative formulation and solution strategy for multicommodity network flow problems. Telecomm. Systems (1995) 3:239–258Crossref, Google Scholar
• Bellman R. E. On a routing problem. Quart. Appl. Math. (1958) 16:87–90Crossref, Google Scholar
• Bertsekas D. P., Pallottino S., Scutellà M. G. Polynomial auction algorithms for shortest paths. Comput. Optim. Appl. (1995) 4(2):99–125Crossref, Google Scholar
• Carré B. A. A matrix factorization method for finding optimal paths through networks. IEE Conf. Publ. (Comput.-Aided Design) (1969) 51:388–397Google Scholar
• Carré B. A. An algebra for network routing problems. J. Inst. Math. Appl. (1971) 7:273–294Crossref, Google Scholar
• Cherkassky B. V., Goldberg A. V., Radzik T. Shortest paths algorithms: Theory and experimental evaluation. Math. Programming (1996) 73(2):129–174Crossref, Google Scholar
• Dantzig G. B. On the shortest route through a network. Management Sci. (1960) 6:187–190Link, Google Scholar
• Dial R. Algorithm 360 shortest path forest with topological ordering. Comm. ACM (1965) 12:632–633Crossref, Google Scholar
• Dijkstra E. W. A note on two problems in connection with graphs. Numerische Mathematik (1959) 1:269–271Crossref, Google Scholar
• Duff I. S., Erisman A. M., Reid J. K.Direct Methods for Sparse Matrices (1989) (Oxford University Press, New York) Google Scholar
• Floyd R. W. Algorithm 97, shortest path. Comm. ACM (1962) 5:345Crossref, Google Scholar
• Ford L. R.Network Flow Theory (1956) (The RAND Corp., Santa Monica, CA) Google Scholar
• Fredman M. L. New bounds on the complexity of the shortest path problems. SIAM J. Comput. (1976) 5(1):83–89Crossref, Google Scholar
• Galil Z., Margalit O. All pairs shortest paths for graphs with small integer length edges. J. Comput. System Sci. (1997) 54(2):243–254Crossref, Google Scholar
• Glover F., Glover R., Klingman D. Computational study of an improved shortest path algorithm. Networks (1984) 14(1):25–36Crossref, Google Scholar
• Goldberg A. V., Radzik T. A heuristic improvement of the Bellman-Ford algorithm. Appl. Math. Lett. (1993) 6(3):3–6Crossref, Google Scholar
• Goldfarb D., Jin Z. An o(nm)-time network simplex algorithm for the shortest path problem. Oper. Res. (1999) 47(3):445–448Link, Google Scholar
• Goldfarb D., Hao J., Kai S. R. Efficient shortest path simplex algorithms. Oper. Res. (1990) 38(4):624–628Link, Google Scholar
• Hu T. C. A decomposition algorithm for shortest paths in a network. Oper. Res. (1968) 16:91–102Link, Google Scholar
• Johnson E. L. On shortest paths and sorting. Proc. ACM 25th Annual Conf. (1972) 510–517Crossref, Google Scholar
• Markowitz H. M. The elimination form of the inverse and its application to linear programming. Management Sci. (1957) 3:255–269Link, Google Scholar
• Mills G. A decomposition algorithm for the shortest-route problem. Oper. Res. (1966) 14:279–291Link, Google Scholar
• Moore E. F. The shortest path through a maze. Proc. Internat. Sympos. Theory Switching, Part II (1957) (The Annals of the Computation Laboratory of Harvard University, Harvard University, Cambridge, MA) 285–292Google Scholar
• Nakamori M. A note on the optimality of some all-shortest path algorithms. J. Oper. Res. Soc. Japan (1972) 15(4):201–204Google Scholar
• Pallottino S. Shortest-path methods: Complexity, interrelations and new propositions. Networks (1984) 14:257–267Crossref, Google Scholar
• Pallottino S., Scutellà M. G. Dual algorithms for the shortest path tree problem. Networks (1997) 29(2):125–133Crossref, Google Scholar
• Pape U. Implementation and efficiency of Moore algorithms for the shortest root problem. Math. Programming (1974) 7:212–222Crossref, Google Scholar
• Rose D. J., Tarjan R. E. Algorithmic aspects of vertex elimination on directed graphs. SIAM J. Appl. Math. (1978) 34(1):176–197Crossref, Google Scholar
• Seidel R. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. System Sci. (1995) 51(3):400–403Crossref, Google Scholar
• Takaoka T. A new upper bound on the complexity of the all pairs shortest path problem. Inform. Processing Lett. (1992) 43(4):195–199Crossref, Google Scholar
• Wang I. L. On implementation of new multiple shortest paths algorithms. (2005) . Technical Report NCKU-IIM-001, Dept. of Industrial and Information Management, National Cheng Kung UniversityGoogle Scholar
• Warshall S. A theorem on Boolean matrices. J. ACM (1962) 9:11–12Crossref, Google Scholar
• Zwick U. All pairs shortest paths in weighted directed graphs—Exact and almost exact algorithms. Proc. 39th Annual IEEE Sympos. Foundations Comput. Sci. (1998) Palo Alto, CA:310–319Crossref, Google Scholar