2026-08-25T22:08:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27336 2026-08-24T14:08:30Z ddc:004 open_access

A Coalgebraic Dijkstra Algorithm (Invited Talk) Sanada, Takahiro Montacute, Yoàv Phalakarn, Kittiphon Hasuo, Ichiro Coalgebra Greatest fixed point Dijkstra’s algorithm Shortest path The Dijkstra algorithm is a classical method for solving the shortest path problem on weighted graphs. There are several variations of the Dijkstra algorithm, including algorithms for the widest path problem and for two-player games. In this paper, we introduce the coalgebraic shortest path problem (CSPP), a unifying framework for a broad class of optimization problems on state-transition systems. This framework encompasses not only the aforementioned problems but also new ones such as the shortest binary tree problem. We further present a coalgebraic Dijkstra algorithm for solving the CSPP efficiently under a suitable condition. Our condition is necessary and sufficient for the algorithm to return correct solutions, thereby providing a precise criterion for when Dijkstra-style acceleration is possible. We also show that the proposed algorithm achieves asymptotic complexity comparable to that of the classical Dijkstra algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takahiro Sanada and Yoàv Montacute and Kittiphon Phalakarn and Ichiro Hasuo 2026 Is Part Of LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2026.5 urn:nbn:de:0030-drops-273365 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.5 eng https://creativecommons.org/licenses/by/4.0/legalcode