Dijkstra的算法具有时间表和不同的缺失边缘

Question

我知道Dijkstra的算法是“最短路径”问题的流行解决方案，但是在实现时间表时它似乎是适得其反的。

假设我有以下权重的图表（从一个点到另一个点的时间）：

A-----C     A->C: 10
\--B--/     A->B: 5
            B->C: 5

如果你将它扔进Dijkstra，它将返回路线A-> C.直到你提到一个时间表来说这很好，这个时间表说路线A-> C只存在于某个时间范围内。如果请求的时间范围超出使用该边缘的范围，则可以轻松删除A-> C边缘。但显然我正在使用的数据集有很多其他方法可以从A-> C获得更高的成本。更不用说如果你想从Z-> Y获得什么，这需要从中间的A-> C。它似乎不是一个理想的解决方案。

除了Dijkstra之外，还有更好的方法来创造一条最短路径，同时还要考虑时间表吗？或者，在找到最佳路径时，是否应修改算法以考虑两个权重？

如果重要，我正在使用python。

[编辑]

时间表是一个基本表格，表示火车（在我的情况下）从A点离开（比方说）12点，然后从B点离开12点05分，然后在12点10分离开C点。当它没有停在B时，它的列是空的，A将是08:00，C将是08:10

A       B        C
800            8:10
12:00  12:05  12:10 

Answer 1

一种方法是创建一组树，表示给定节点之间的所有简单路径，并且只选择那些不包含不推荐边缘的最短路径。您可以通过调整Dijkstra的算法或其他算法（如DFS或BFS）来查找所有路径。同时查找两个节点之间的所有路径都被认为是一个难题，但根据您的需要和您正在处理的图形类型，您可以创建所需的图形。你也可以阅读这篇关于此事的帖子。 - > Find all paths between two graph nodes。即你可以拥有一组有限的路径（如果使用Dijkstra top N shortest）。

现在为优化此步骤，以便找出是否弃用了边缘，我建议将所有边缘ID或名称的字典作为键，将其弃用时间戳作为值，然后通过将值与now().timestamp()进行比较并在每次查找后过滤字典只需从字典中删除项目。另请注意，在开始过滤之前，应检查边缘是否存在于字典中（为了防止算法对重复边缘多次运行过滤）。

代码应如下所示：

def filter_edge(u_id):
    if edge in deprecation:
        time_stamp = deprecation[u_id]
        if time_stamp > datetime.now().timestamp():
            return True
    return False

路径验证如下：

def validate_path(path):
    return not any(filter_edge(edge.id) for edge in path)