Dijkstra检查站

Question

我实现了一个名为 dijkstra() 的函数，returns 是从起点到终点的最短路径。我想添加一个修改，以便路径通过特定节点。结果是这样的：

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 算法的实现通常会计算到所有可能目的地的最短路径。

这表明您可以：

将检查点设置为算法的起点
运行 dijkstra 从这个起点开始一次
将起点到检查点的最短路径与起点到目的地的最短路径合并

这仅适用于无向图，并假定一条边可以多次使用。

您可能还会发现，一旦找到目标节点，该实现就会终止，因此您需要将其修改为仅在找到两个最终点后才终止。

Answer 2

如果问题允许您在路径中有循环并且只有一个 检查点。然后你的解决方案可以在时间复杂度不变的情况下解决问题（虽然操作次数更多，但不重要）。
如果不允许循环，您的解决方案将失败。想想下面的例子：

如果您尝试找到从 A 到 B 的最短路径，您将得到长度为 1 的路径。如果您尝试找到从 B 到 B 的最短路径C，你会得到长度为3的路径。但是，它需要你通过点A。所以你的解会有一个循环。

解决方案：修改您的 Dijkstra，以便首先调用 returns 访问节点列表，然后第二次调用获取这些节点并将它们从图中删除，这样我们就可以保证我们的路径中没有循环。然而，这种方法是有风险的，因为我们可以通过不访问在先前 Dijkstra 调用中访问过的节点来消除最短路径。第二种方法是做同样的事情：
从 A 调用 Dijkstra 到 B 并且 return 访问了节点
从 B 到 C 调用 Dijkstra，消除已访问的节点
将路径的长度存储在变量中
从 B 调用 Dijkstra 到 C 并且 return 访问了节点
从 A 到 B 调用 Dijkstra，消除访问过的节点
将路径的长度存储在变量中
比较长度和 return 与最短路径关联的路径。

Dijkstra检查站

Dijkstra checkpoint

algorithm

time-complexity

dijkstra