database - 存储路由数据

Question

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

开始位置（时间）-> 停止 1（时间1）-> 停止 2（时间2）-> ...结束位置

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

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

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

开始位置：x，结束位置：y，时间：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)