层级捷径图构建中复用Dijkstra结果初始化有界搜索的正确性探讨

一、复用距离图与优先队列初始化Dijkstra的注意事项 #

• 清理优先队列冗余条目：前层优先队列中可能存在节点的旧距离条目（比如节点u的旧距离d_old，但距离图中已存储更优的d_new < d_old）。直接复用队列会导致这些旧条目被处理，虽然算法会因d(u) < 队列条目距离自动跳过，但会增加无意义的开销。建议复用前清理冗余条目，或使用带过时标记的优先队列（处理时跳过已失效的条目）——C++标准库priority_queue不支持递减键，可通过额外的标记数组实现。
• 确保距离图的最短路径有效性：复用的距离值必须是严格的最短路径距离（前层在r'=8^(i-1)下得到的结果满足这一点）。对于距离图中仍为无穷大的节点，说明前层范围内无法到达，当前层需正常处理。
• 维持终止条件的正确性：当前有界Dijkstra的终止条件是「队列中最小距离超过r=8^i，或所有可到达且距离≤r的节点完成松弛」。不能因初始队列元素均≤r'就提前终止，需持续处理直到满足终止条件。
• 保留已处理节点的标记：前层标记为「已处理」的节点，其最短距离已确定，无需重置标记或重新处理。根据Dijkstra的最优子结构，这些节点的邻接边松弛逻辑不受影响，不会破坏正确性。

二、基于已知小于r的最短距离启动有界Dijkstra的可行性 #

完全可行，核心前提是已知的距离必须是严格的最短路径距离，而非近似值。具体操作要点：

• 将已知的d(s, v) < r直接填入距离图，将未标记为「已处理」的节点(v, d(s,v))加入优先队列（已处理节点的最短距离已确定，无需重复入队）。
• 这种复用完全符合Dijkstra算法的最优子结构性质，能够有效减少重复计算量，尤其是前层已覆盖的短路径节点，无需重新从源点s开始搜索。

内容的提问来源于stack exchange，提问作者maitrehihois