Summary
The best algorithm for finding the shortest paths between every pair of vertices in a complete graph is the triple algorithm. This algorithm can be described algebraically as an operation of a category on the set of real valued finite directed graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Literatur
Ehresmann, C.: Catégories et structures. Paris: Dunod 1965.
Floyed, R.W.: Algorithm 97, shortest paths. Commun. Assoc. comput. Machin. 5, 345 (1962).
Hu, T.C.: A decomposition algorithm for shortest paths in a network. Operations Res. 16, 91–102 (1968).
Murchland, J.D.: A new method for finding all elementary paths in a complete directed graph, LSE-TNT-22. London School of Economics, Oct. 1965.
Warshall, S.: A theorem on Boolean matrices. J. Assoc. comput. Machin. 9, 11–13 (1962).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hammer, G. Eine Bemerkung zum Tripel-Algorithmus zur Bestimmung der kürzesten Wege in einem Graphen. Z. Wahrscheinlichkeitstheorie verw Gebiete 12, 153–154 (1969). https://doi.org/10.1007/BF00531647
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00531647