26

我有一个公共汽车/火车/...站点的数据库以及每个日期的到达/离开时间等等。我正在寻找一种方法来搜索两个位置之间的最快（最短/最便宜/最少的转换）行程。我希望将来有任意位置，使用 OpenStreetMap 数据在站点之间和从站点到开始/结束之间行走，但是目前我只想在数据库中找到两个站点之间的路径。

问题是我似乎找不到关于这个主题的太多信息，例如这个维基百科页面有很多文本，其中绝对没有有用的信息。

我发现的是在Google Transit中使用的GTFS格式。虽然我的城市不提供公共数据馈送（甚至不提供私人数据馈送），但我已经拥有 GTFS 包含的所有重要信息，因此进行转换将是微不足道的。

有一些基于 GTFS 的软件，比如OpenTripPlanner，它也可以使用OpenStreetMap进行行人/汽车/自行车路线。

但是，路由代码没有很好的文档记录（至少从我发现），我不需要整个事情。

我正在寻找的只是对我可以使用的算法的一些很好的概述，它们的性能，也许是一些伪代码。

所以，问题是，给定站点、路线和到达/出发/旅行时间的列表，我怎样才能轻松找到从站点 A 到站点 B 的最快路径？

4

1 回答 1

16
  1. 将您的问题建模为图形。每个车站都是一个顶点，每辆公共汽车/火车都是一个边缘。
  2. 创建一个函数w:Edges->R，指示每个边的时间/金钱/...。
  3. 现在，您有一个典型的最小路径问题，可以通过 Dijkstra 算法解决，该算法从给定源找到所有顶点的最小路径。

(*) 对于“最少转换”，您的每个边的权重实际上是 1，因此您甚至可以通过运行BFS甚至双向BFS 而不是 dijkstra 来优化它，正如我在这篇文章中解释的那样 [It is explain for social距离，但实际上是相同的算法]。

编辑
作为对您在评论中提到的图表的非静态性质[时间]的编辑[对于价格和转换次数，我上面提到的仍然适用，因为这些图表是静态的]，您可以使用距离向量路由算法，实际上适用于动态图，是Bellman Ford 算法的分布式变体。
算法思路：

  • 周期性地，每个顶点将其“距离向量”发送给它的邻居[该向量表示从发送顶点到另一个顶点的“成本”。
  • 它的邻居尝试更新他们的路由表[最好通过哪个边缘移动到每个目标]
  • 对于您的情况，每个节点都知道到达其邻居的最快方式是什么，[行程时间 + 等待时间]，并且它 [顶点/站] 将此数字添加到距离向量中的每个主菜，以便知道如何以及到达目的地需要多少时间。当一辆公共汽车离开时，应该重新计算所有节点的行程时间[来自这个来源]，并且应该将新向量发送给它的邻居
于 2011-08-30T15:43:34.770 回答