一个城市有很多车站，它们由火车线路或/和公交线路连接。有一些时间表描述了车站之间的旅行。
类可以是:
地点(名称、图片、位置...)
时间表(从_地点，到_地点，距离，出发_时间，到达_时间，...)
我需要实现如下功能:
getRoutes(from_place, to_place, departure_time){ ....
该函数需要返回前 5 条最快的路线(一条路线是一组时间表)。
还有一点:旅客可以在同一站换乘其他车辆，换乘时间不予考虑。
我该怎么做？
谢谢!
最佳答案
这似乎可以通过修改后的 Dijkstra 解决，其中从 A 到 B 的边成本不是静态的，而是取决于到达 A 的时间(您将使用时间而不是距离)，并且边权重反射(reflect)使用下一个可用的最快到达时间表到达 B 所需的时间。在运行结束时，您将以从开始到结束的最快路线结束。
为了找到更远的路线，有几个选项。一个简单的方法是采用最快路线的 k 段(时刻表)，对于这些段中的每一个，
- 删除它
- 重新运行修改后的 dijkstra 以找到没有该路段的最快路线
- 加回去
请注意，在完成所有 k 次运行之前，您无法知道哪个段删除会导致更快的次优到达。将 k 中最短的一段作为次佳路线后，您可以通过对次佳的 t 路段重复此过程来寻找第三佳路线路线(如果找到下一个竞争者，则丢弃第一条最佳路线)。
另一种计算从开始到结束的n最佳路线的方法是进一步修改时间感知的 Dijkstra 以不仅存储每个节点的最佳到达时间(和父调度)；但要存储此类到达时间和路线的列表(按到达时间排序)。在结束节点中，此列表将反射(reflect)所有最短路径，唯一的缺点是，在第一次到达结束节点时您不会中断 Dijkstra，而是需要继续运行直到到达 n 次。请注意，根据您对“不同路线”的定义，从头到尾可能不会有 5 条不同的路线。
关于algorithm - 根据时间表的旅行路线算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47903719/