r - R/Python/Matlab 中带动态权重的最短路径图(重复 Dijkstra？距离矢量路由算法？)

Question

我有一张平均道路网络图。全天变化的交通速度措施。节点是道路上的位置，边连接同一条道路上的不同位置或两条道路之间的交叉点。我需要一种算法来求解给定开始时间的任意两个节点之间的最短行程时间路径。

显然，该图具有动态权重，因为边 i 的行程时间是该边交通速度的函数，这取决于您的路径到达边所需的时间 < em>我。

我已经实现了 Dijkstra 算法 边权重 = (edge_distance/edge_speed_at_start_time) 但这忽略了边缘速度随时间的变化。

我的问题是:

1. 是否有一种启发式方法可以重复调用 Dijkstra 算法来逼近真实解？

2. 我相信“距离矢量路由算法”是解决此类问题的正确方法。有没有办法使用 Igraph 库或 R、Python 或 Matlab 中的其他库来实现此算法？

编辑 我目前在 R 中使用 Igraph。该图是一个 igraph 对象。 igraph 对象是使用 igraph 命令 graph.data.frame(Edges) 创建的，其中 Edges 看起来像这样(但有更多的行):

我还有一个每次每条边的速度(以 MPH 为单位)的矩阵，它看起来像这样(除了更多的行和列):

因为我想找到最短的旅行时间 路径，所以给定边的权重是 edge_distance/edge_speed。但是 edge_speed 会根据时间而变化(即你已经在这条路上行驶了多长时间)。 该图有 7048 个节点和 7572 条边(因此非常稀疏)。

Answer 1

存在解决此问题的精确算法!它被称为时间相关的 Dijkstra (TDD)，运行速度与 Dijkstra 本身一样快。

不幸的是，据我所知，igraph 和 NetworkX 都没有实现这个算法，因此您必须自己编写一些代码。

幸运的是，您可以自己实现!您需要在一个地方调整 Dijkstra。 在正常的 Dijkstra 中，您按如下方式分配权重: 使用 dist 您当前的距离矩阵，u 您正在考虑的节点和 v 它的邻居。

alt = dist[u] + travel_time(u, v)

在时间相关的 Dijkstra 中，我们得到以下内容:

current_time = start_time + dist[u]
cost = weight(u, v, current_time)
alt = dist[u] + cost

TDD Dijkstra 由 Stuart E. Dreyfus 描述。一些最短路径的评估 算法。运筹学, 17(3):395–412, 1969

目前，已经使用了更快的启发式算法。可以通过搜索词找到它们:“时间相关路由”。