On computing sets of shortest paths in a graph

ABSTRACT

Two algorithms are presented that construct the k shortest paths between every pair of vertices in a directed graph. These algorithms generalize the Floyd algorithm and the Dantzig algorithm for finding the shortest path between every pair of vertices in a directed graph.

REFERENCES

• 1: Bellman, R. and Kalaba, R. On kth best policies. SIAM 8 (1960), 582-588.
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: Clarke, S., Krikorian, A., and Rausen, J. Computing the N best loopless paths in a network. SIAM 11 (1963), 1096-1102.
• 4: Dantzig, G. All shortest routes in a graph. In Theories des Graphes, Proc. Internat. Symp., Rome. Dunod, Paris, 1966, pp. 91-92.
• 5: Dijkstra, E. A note on two problems in connection with graphs. Numerische Mathematik I (1959), 269-71.
• 6: Dreyfus, S. An appraisal of some shortest-path algorithms. ORSA 17 (1969), 395-412.
• 7: Elmaghraby, S. Theory of networks and management science. Mgmt. Sci. 17 (1970), 1-34.
• 8: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 9: Seymour Ginsburg, Introduction to Mathematical Machine Theory, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1982
• 10: Walter Hoffman , Richard Pavley, A Method for the Solution of the Nth Best Path Problem, Journal of the ACM (JACM), v.6 n.4, p.506-514, Oct. 1959 [doi>10.1145/320998.321004]
• 11: Minieka, E., and Shier, D. A note on an algebra for the k best routes in a network. J. Inst. Math. Appl. 11 (1973) 145-149.
• 12: Murchland, J. A new method for finding all elementary paths in a complete directed graph. Rept. LSE-TNT-22, Transport Network Theory Unit, London School of Economics, London, 1965.
• 13: Pollack, M. Solutions of the kth best route through a network -a review. J. Math. Anal. and Appl. 3 (1961), 547-549.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms

Keywords:
algorithm, graph, network, shortest path