一个城市有许多车站,它们通过火车线路或/和公交线路连接。有一些时间表描述了站之间的旅行。
课程可以是:
地点(名称,图像,位置......)
时间表(from_place,to_place,distance,departure_time,arrival_time,...)
我需要实现如下函数:
getRoutes(from_place,to_place,departure_time){....}
该函数需要返回前5个最快的路由(路由是一组时间表)。
还有一件事:旅行者可以转移到同一车站的其他车辆,转移时间将不予考虑。
我该怎么做?
谢谢!
这似乎可以通过修改后的Dijkstra解决,其中从A到B的边缘成本不是静态的,而是取决于达到A的时间(您将使用时间而不是距离),并且边权重反映了所需的时间使用下一个可用的最快到达时间表到达B.在运行结束时,您将从头到尾以最快的路线结束。
为了找到更多路线,有几个选择。一个简单的方法是采用最快路线的k段(时间表),对于每个段,
请注意,在完成所有k次运行之前,您无法知道哪个分段删除将导致更快的第二次到达。在以最短的k次运行作为第二最佳路线之后,您将通过在第二最佳路线中使用t段重复此过程来寻找第三最佳路线(丢弃第一最佳路线,如果找到,为下一个竞争者)。
从开始到结束计算n个最佳路线的另一种方法是进一步修改时间感知Dijkstra,以便不仅将最佳到达时间(和父时间表)存储到每个节点;但要存储这些到达时间和路线的清单(按到货时间排序)。在结束节点中,此列表将反映所有最短路径,唯一的缺点是,当首次到达完成节点时,您需要继续运行直到达到第n次时才会中断Dijkstra。请注意,根据您对“不同路线”的定义,从开始到结束可能没有5条不同的路线。