database - 存储路线数据

Question

我有许多火车网络的时间表，其形式为 -

Start Location (Time) -> Stop 1 (time1) -> Stop 2 (time2) -> ... End Location

即每条路线/时间表都由一系列按上升时间发生的停靠点组成。这些路线每天重复多次。

最终，我想在此数据之上构建一个寻路算法。最初这将从单个时间表/路线返回路径。但最终我希望能够计算出跨越一条以上路线的最佳旅程。

因此，我的问题是，存储此数据以使查询路线尽可能简单的最佳方式是什么？我想象查询的格式是...

Start Location: x, End Location: y, At Time: t

Answer 1

如果您正在进行寻路，许多寻路算法处理跟随最短路径段到下一个节点，并从该节点查询路径。因此，您的查询最终将是，在时间 t 或之后来自站点 x 的所有路段，但对于给定的不同目的地是最早的路段。

如果您有从华盛顿特区到巴尔的摩的路线，您的第 1 站和第 2 站可能是新卡罗尔顿和阿伯丁。所以你可以存储:

id (auto-increment), from_station_id, to_station_id, departure_time, arrival_time

您可以存储一条从华盛顿到新卡罗尔顿的记录，一条从新卡罗尔顿到阿伯丁的记录，以及一条从阿伯丁到巴尔的摩的记录。但是，如果 (a) 它们是您旅行计划的可能出发地和目的地，或者 (b) 有一些重要的连接路线(不仅仅是下火车和乘坐同一路线的下一类火车)，我只会包括这些站点.

您的寻路算法将有一个步骤(在一个循环中)从当前成本最低的节点开始(最早到达)下一个路段列表，以及该路段将您带到的节点。

select segments.*
from segments inner joint segments compare_seg on segments.to_station_id = compare_seg.station_id
where departure_time > ?
group by segments.id
having segment.arrival_time = min(compare_seg.arrival_time)