Thorups 算法

用于无向图的单源最短路径的 Thorup 算法具有时间复杂度 O(m)，低于 Dijkstra。

基本思路如下。 （对不起，我还没有尝试实现它，所以我可能会错过一些小细节。原始论文是支付给我的，所以我试图从引用它的其他来源重建它。如果你可以验证，请删除这个评论。）

• 有办法在 O(m) 中找到生成树（此处未描述）。你需要将生成树从最短边缘增长到最长边，并且在完全成长之前它将是具有多个连接组件的森林。
• 选择一个整数 b（b> = 2）并仅考虑长度限制为 b ^ k 的生成林。合并完全相同但具有不同 k 的组件，并将组件的级别称为最小 k。然后在逻辑上将组件制作成树。如果 u 是与 v 完全包含 v 的最小组件，则 u 是 v 的父项。根是整个图形，叶子是原始图形中的单个顶点（负无穷大级别）。树仍然只有 O(n) 个节点。
• 保持每个组件到源的距离（如 Dijkstra 算法）。具有多个顶点的组件的距离是其未展开的子项的最小距离。将源顶点的距离设置为 0 并相应地更新祖先。
• 考虑基数 b 的距离。当第一次访问级别 k 中的节点时，将其子节点放入由级别 k 的所有节点共享的桶中（如在桶排序中，将 Dijkstra 算法中的堆替换为数字 k 及其距离的更高）。每次访问节点时，只考虑其第一个桶，访问并删除每个桶，更新当前节点的距离，并使用新距离将当前节点重新链接到其父节点，并等待下一次访问以下桶。
• 当访问叶子时，当前距离是顶点的最终距离。展开原始图形中的所有边缘并相应地更新距离。
• 重复访问根节点（整个图形），直到到达目的地。

它基于以下事实：在生长森林的两个连接组件之间没有长度小于 l 的边缘，长度限制为 l，因此，从距离 x 开始，你可以只关注一个连接的组件，直到达到距离 x + l。在访问具有较短距离的顶点之前，你将访问一些顶点，但这并不重要，因为已知从这些顶点到此处不会有更短的路径。其他部分的工作类似于桶排序/ MSD 基数排序，当然，它需要 O(m) 生成树。