Dijkstra检查站

Question

我实现了一个名为dijkstra()的函数，它返回从原点到目的地的最短路径。我想添加一个修改，以便路径通过特定的节点。其结果是：

def checkpoint(G, origin, destination, extra):

    path1 = dijkstra(G,origin,extra)['path'] # returns a list with the path
    path2 = dijkstra(G,extra,destination)['path'] 
    
    path = path1 + path2
    
    return path

我用优先级队列实现了dijkstra，所以复杂度是O(E +V log(V))。

我的问题是:有没有更有效的方法来解决这个问题？检查点功能的复杂性是什么？

Answer 1

Dijkstra算法的一个实现通常计算到所有可能的目的地的最短路径。

这表明你可以：

1. 将检查点设置为算法
2. Run dijkstra的起点，从这个起点开始，
3. 将从起点到检查点的最短路径与从起点到目标

的最短路径组合在一起。

这将只适用于无向图，并假设一个边可以使用不止一次。

您可能还会发现，一旦找到目标节点，该实现就会立即终止，因此您需要修改它，使其只在找到两个最终点之后才终止。