Dijkstra实现途经指定节点最短路径的优化方案及复杂度咨询

现有逻辑正确性说明 #

你当前的实现逻辑是正确的：根据最短路径的最优子结构性质，必须途经指定节点的最短路径，必然可以拆分为起点到途经点的最短路径和途经点到终点的最短路径两段，拼接结果符合需求。
唯一需要注意的小问题是路径拼接会重复途经点：path1的最后一个元素和path2的第一个元素都是extra，可以修改为path = path1 + path2[1:]去掉重复节点。

# 优化后的拼接逻辑
def checkpoint(G, origin, destination, extra):
    path1 = dijkstra(G,origin,extra)['path']
    path2 = dijkstra(G,extra,destination)['path']
    path = path1 + path2[1:] # 去掉重复的途经点
    return path

当前checkpoint函数的时间复杂度 #

你用的优先队列实现的Dijkstra单次时间复杂度为O(E + V log V)，当前实现调用了2次Dijkstra，因此整体渐近时间复杂度仍为O(E + V log V)，仅常数项是单次Dijkstra的2倍，不会改变复杂度量级。

更高效率的实现方案 #

• 渐近复杂度层面：单途经点场景下没有更优的方案，因为求解该问题的下界就是需要两次单源最短路径计算，和当前实现的复杂度量级一致，无法再降低复杂度。
• 工程层面的常数优化：
  • 如果是无向图场景，两次Dijkstra计算没有依赖关系，可以并行执行，运行耗时可以压缩到接近单次Dijkstra的水平。
  • 如果后续需要扩展支持多个途经点的场景，当前的两次调用方案不再适用，需要先计算所有关键点（起点、所有途经点、终点）两两之间的最短路径，再通过动态规划求解最优的途经点访问顺序。

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