David Anekstein展示了如何在代数图表示上直接执行Dijkstra算法，而无需转换为邻接表，从而避免O(n^2)的边物化。该方法以O(s log s)时间运行，其中s为代数图表达式大小，扩展了之前关于代数图泛型递归的研究成果。
背景
alga库为Haskell提供了代数图数据结构，通过组合算子而非显式邻接结构来表示图。本文继续研究能够在紧凑表示上高效运行的算法。
- 来源
- Lobsters
- 发布时间
- 2026年9月15日 20:04
- 评分
- 7.0 / 10
David Anekstein展示了如何在代数图表示上直接执行Dijkstra算法，而无需转换为邻接表，从而避免O(n^2)的边物化。该方法以O(s log s)时间运行，其中s为代数图表达式大小，扩展了之前关于代数图泛型递归的研究成果。
alga库为Haskell提供了代数图数据结构，通过组合算子而非显式邻接结构来表示图。本文继续研究能够在紧凑表示上高效运行的算法。