首页 文章

R / Python / Matlab中具有动态权重（重复Dijkstra？距离矢量路由算法？）的图形最短路径

提问于
浏览 次
2

我有一个平均道路网络的图表 . 交通速度衡量一整天都在变化 . 节点是道路上的位置，边缘连接同一道路上的不同位置或两条道路之间的交叉点 . 我需要一种算法，它可以在给定开始时间的情况下解决任意两个节点之间的最短行程时间路径 .

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

我已经使用边权重=（edge_distance / edge_speed_at_start_time）实现了Dijkstra算法，但这忽略了边缘速度随时间变化 .

我的问题是：

  • 是否有一种启发式方法可以使用对Dijkstra算法的重复调用来逼近真正的解？

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

EDIT 我目前在R中使用Igraph . 图是一个igraph对象 . igraph对象是使用igraph命令graph.data.frame（Edges）创建的，其中Edges看起来像这样（但有更多行）：

enter image description here

我还有每个边缘的速度矩阵（以MPH为单位），看起来像这样（除了有更多的行和列）：

enter image description here

由于我想找到最短的旅行时间路径，因此给定边缘的权重是edge_distance / edge_speed . 但是edge_speed会随着时间的变化而变化（也就是说，你的时间长得很稀疏） .

r matlab graph igraph shortest-path

1 回答

  • 0

    R中的igraph包怎么样？您可以尝试get.shortest.paths或get.all.shortest.paths函数 .

    library(igraph)
?get.all.shortest.paths
get.shortest.paths()
get.all.shortest.paths()# if weights are NULL then it will use Dijkstra.
    回复于

相关问题