{"id":"arxiv:2605.22149","kind":"preprint","title":"A Coalgebraic Dijkstra Algorithm","authors":["Takahiro Sanada","Yoàv Montacute","Kittiphon Phalakarn","Ichiro Hasuo"],"author_count":4,"year":2026,"published":"2026-05-21","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2605.22149","nct_id":null,"source_url":"https://arxiv.org/abs/2605.22149","archive_url":"https://space-kitty.com/papers/arxiv:2605.22149","updated":"2026-05-21","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2605.22149","abstract":"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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}