{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T02:30:48Z","timestamp":1775097048583,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4-6","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Around 1960, Dijkstra, Floyd and Warshall published papers on algorithms for solving single-source and all-sources shortest path problems, respectively. These algorithms, nowadays named after their inventors, are well known and well established. This paper sheds an algebraic light on these algorithms. We combine the shortest path problems with Kleene algebra, also known as Conway\u2019s regular algebra. This view yields a purely algebraic version of Dijkstra\u2019s shortest path algorithm and the one by Floyd\/Warshall. Moreover, the algebraic abstraction yields applications of these algorithms to structures different from graphs and pinpoints the mathematical requirements on the underlying cost algebra that ensure their correctness.<\/jats:p>","DOI":"10.1007\/s00165-012-0245-4","type":"journal-article","created":{"date-parts":[[2012,6,28]],"date-time":"2012-06-28T08:35:50Z","timestamp":1340872550000},"page":"459-476","source":"Crossref","is-referenced-by-count":34,"title":["Dijkstra, Floyd and Warshall meet Kleene"],"prefix":"10.1145","volume":"24","author":[{"given":"Peter","family":"H\u00f6fner","sequence":"first","affiliation":[{"name":"NICTA, Sydney, Australia"},{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"M\u00f6ller","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Augsburg, Augsburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"publisher","DOI":"10.5555\/578775"},{"key":"e_1_2_1_2_2_2","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/15.2.161"},{"key":"e_1_2_1_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(94)90005-1"},{"key":"e_1_2_1_2_4_2","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_1_2_5_2","unstructured":"Berge C (1962) The theory of graphs and its applications. Methuen"},{"key":"e_1_2_1_2_6_2","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/7.3.273"},{"key":"e_1_2_1_2_7_2","volume-title":"Graphs and networks.Oxford applied mathematics and computing science series","author":"Carr\u00e9 B","year":"1979"},{"key":"e_1_2_1_2_8_2","doi-asserted-by":"crossref","unstructured":"Coltun R Ferguson D Moy J (2008) OSPF for IPv6. RFC 2328 (Standard Errata Exist)","DOI":"10.17487\/rfc5340"},{"key":"e_1_2_1_2_9_2","unstructured":"Conway J (1971) Regular algebra and finite machines. Chapman and Hall London"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.2.187"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_2_12_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809088"},{"key":"e_1_2_1_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_2_14_2","unstructured":"Gondran M Minoux M (1979) Graphes et\u00a0algorithmes. Eyrolles"},{"key":"e_1_2_1_2_15_2","unstructured":"Gondran M Minoux M (1988) Graphs and Algorithms. Wiley"},{"key":"e_1_2_1_2_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/1386688"},{"key":"e_1_2_1_2_17_2","first-page":"212","volume-title":"Relations and Kleene algebra in computer science, lecture notes in computer science, vol 6663","author":"H\u00f6fner P","year":"2011"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"crossref","unstructured":"Hollenberg M (1998) Equational axioms of test algebra. In: Nielsen M Thomas W (eds) CSL \u201997: selected papers from the 11th international workshop on computer science logic lecture notes in computer science vol 1414","DOI":"10.1007\/BFb0028021"},{"key":"e_1_2_1_2_19_2","first-page":"279","volume-title":"Automated deduction, lecture notes in artificial intelligence, vol 4603","author":"H\u00f6fner P","year":"2007"},{"key":"e_1_2_1_2_20_2","unstructured":"Kleene S (1951) Representation of events in nerve nets and finite automata. Technical Report RM-704 RAND Corporation RAND Research Memorandum"},{"key":"e_1_2_1_2_21_2","unstructured":"Kleene SC (1952) Introduction to metamathematics. Van Nostrand"},{"key":"e_1_2_1_2_22_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1037"},{"key":"e_1_2_1_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_2_1_2_24_2","doi-asserted-by":"crossref","unstructured":"Lengauer T Theune D (1991) Efficient algorithms for path problems with general cost citeria. In: Leach Albert J Burkhard Monien B Rodr\u00edguez-Artalejo M (eds) Automata languages and programming 18th International colloquium ICALP91 Madrid Spain July 8\u201312 1991 proceedings. Lecture notes in computer science vol 510. Springer Berlin pp 314\u2013326","DOI":"10.1007\/3-540-54233-7_144"},{"key":"e_1_2_1_2_25_2","doi-asserted-by":"crossref","unstructured":"Lengauer T Theune D (1991) Unstructured path problems and the making of semirings (preliminary version). In: Dehne F Sack J-R Santoro N (eds) Algorithms and data structures 2nd workshop WADS \u201991 Ottawa Canada August 14\u201316 1991 proceedings. Lecture notes in computer science vol 519. Springer Berlin pp 189\u2013200","DOI":"10.1007\/BFb0028261"},{"key":"e_1_2_1_2_26_2","doi-asserted-by":"crossref","unstructured":"Moy J (1998) OSPF version 2. RFC 2328 (Standard Errata Exist)","DOI":"10.17487\/rfc2328"},{"key":"e_1_2_1_2_27_2","unstructured":"Oran D (1990) IS-IS protocol specification (IETF). RFC 1142 (Informational)"},{"key":"e_1_2_1_2_28_2","doi-asserted-by":"crossref","unstructured":"Perkins C Belding-Royer E Das S (2003) Ad hoc on-demand distance vector (AODV) routing. RFC 3561 (Experimental)","DOI":"10.17487\/rfc3561"},{"key":"e_1_2_1_2_29_2","first-page":"216","article-title":"Transitivit\u00e9 et connexit\u00e9","volume":"249","author":"Roy B","year":"1959","journal-title":"Comptes Rendus de l\u2019Acad\u00e9mie des Sci Paris"},{"key":"e_1_2_1_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322272"},{"key":"e_1_2_1_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-012-0245-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00165-012-0245-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s00165-012-0245-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T16:01:33Z","timestamp":1641484893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s00165-012-0245-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":31,"journal-issue":{"issue":"4-6","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1007\/s00165-012-0245-4"],"URL":"https:\/\/doi.org\/10.1007\/s00165-012-0245-4","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}