A Coalgebraic Dijkstra Algorithm
For researchers in optimization and algorithm design, this work provides a general framework and algorithm that unifies and extends Dijkstra-style acceleration to a broad class of problems, with a precise condition for correctness.
The paper introduces the coalgebraic shortest path problem (CSPP), a unifying framework for optimization problems on state-transition systems, and presents a coalgebraic Dijkstra algorithm that solves it efficiently under a necessary and sufficient condition, achieving asymptotic complexity comparable to the classical Dijkstra algorithm.
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.