David Anekstein demonstrates how to perform Dijkstra's algorithm directly on algebraic graph representations without converting them to adjacency maps, avoiding O(n^2) edge materialization. The approach runs in O(s log s) time where s is the algebraic graph expression size, extending earlier work on generic recursion applied to algebraic graphs.
Background
The alga library provides algebraic graph data structures for Haskell, representing graphs through composition operators rather than explicit adjacency structures. This post continues research into efficient algorithms that operate on these compact representations.
- Source
- Lobsters
- Published
- Sep 15, 2026 at 08:04 PM
- Score
- 7.0 / 10