使用 Dijkstra 算法实现时间表
我正在尝试实施一个阅读教练时间表的系统来计划旅程。
这是我的场景：
我只想输入旅行日期、起点站和终点站，但从 A 到 B 可能涉及 3 或 4 个转接旅程，我想返回几个选项，按总数排序所需时间。我的数据库设置有一个车站表、一个旅程表和一个旅程实例表（即包含旅程运行的日期）。
我在 Dijkstra 算法的 C# 中得到了很好的实现，但我发现它是有限的，因为我不知道如何包括在公交车站等待转接旅程的时间，而且许多旅程可以从一个车站到另一个车站另一个在不同时间发生的情况则加剧了混乱。我还必须考虑旅程是否需要一天甚至两天才能完成，事实证明这很麻烦。 Dijkstra 是否值得在这里坚持下去，或者有人知道其他可能更适合的东西吗？
我正在使用 asp.net MVC3、C# 和 EF4，但我在这里追求的并不是太多代码 - 更多只是我最好使用的流程的正确方向上的一点，因为这远远超出了我的任何范围以前做过。 （当我自愿参与这个项目时，我可能贪得无厌！）如果有人可以提供一些建议，或者一些可以帮助解决这种情况的文档的链接，那将有很大帮助。谢谢
I'm trying to implement a system of reading coach timetables to plan a journey.
Here's my scenario:
I'd like to just enter a travel date, a start station and an end station, but to get from A to B, there could be 3 or 4 connecting journeys involved, and I'd like to return several options, ordered by total time required. My database set up has a table for stations, a table for journeys and a table for journey instances (i.e. containing inclusive dates of operation of journeys).
I've got a good implementation in c# of Dijkstra's algorithm, but I find it's limited as I can't figure out how to include time for waiting at bus stations for connecting journeys, and the fact that many journeys can go from one station to another at different times is adding to the confusion. I also have to take into account if the journey takes a day or even 2 to complete, which has proved troublesome. Is Dijkstra's worth persevering with here, or does anyone know of something else that might be better suited?
I'm using asp.net MVC3, C# and EF4, but it's not so much code I'm after here - more just a point in the right direction of the process I'd be best using, as this is well beyond anything I've done before. (I possibly bit off more than I could chew when I volunteered for this project!) If anyone could offer some advice, or a link to some documentation that could help with this situation, that would help enormously. Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
首先：感谢你自愿参与一个雄心勃勃的项目。其次：这可能有点具有挑战性，从下面链接的另一篇 StackOverflow 帖子来看：NP-Complete。
Dijkstra 算法在静态图上找到单源最短路径，但这不是您在这个问题中所做的。由于此类图中的顶点可能存在于重叠的时间空间中，因此从 a1 到 a2 最快的巴士可能会在中午 12:00 出发，但最快的巴士a2 至 a3 可能于当天上午 11:59 出发。那是不可能的。
显然，您已经考虑过这一点，但看待问题的抽象方式是，您并不是试图找到图中的最短路径，而是试图找到有效的三条路径中的最短路径：维度空间（时间作为第三维度）。假设您根据时间对节点进行拓扑排序，则可以将强力方法（对于小图来说仍然很好）实现为广度优先搜索。
相关链接在这里：公交车公共交通算法有关
该主题的一些阅读：
愿原力与你同在。
First off: good on you for volunteering on an ambitious project. Secondly: this may be a tad challenging, and judging from another StackOverflow post linked below: NP-Complete.
Dijkstra's algorithm finds single-source shortest paths on a static graph, but that's not what you're doing in this problem. Since the vertices in such a graph will probably exist in overlapping temporal spaces, the fastest bus from a1 to a2 may leave at 12:00 pm, but the fastest bus from a2 to a3 may leave at 11:59 am the same day. That's a non-starter.
Obviously, you've thought about this, but an abstract way of looking at the problem is that you're not trying to find the shortest path in a graph, but you're trying to find the shortest path in what is effectively three-dimensional space (time as the third dimension). A brute force approach (which is nonetheless fine for small graphs) could be implemented as a breadth first search, assuming you topologically order the nodes according to time.
Related link is here: Bus public transport algorithm
Some reading on the topic:
May the Force be with you.
确实可以修改Dijkstra来找到从A站到B站的最快路线，同时考虑到发车时间和中间站所需的等待。 正如其他答案所声称的那样，它不是 NP 完全的。在下文中，我将假设公交车时刻表是周期性的（即无限期地重复），但它实际上应该足以，对于一天中的每个时间、每个公交车站以及访问该公交车站的每条线路（旅程），快速找到下一个出发点（旅程实例）。
我们将问题建模为有向多重图：公交车站是图的顶点，图中的边是通过某条公交线路从一个公交车站到另一个公交车站的行程。一条边在形式上是一个元组
(u_a, u_b, id, f, w, r)，其中u是源顶点v是目标vertexid是旅程 ID（需要检索实际解决方案 - 留作练习）f是第一次出发时间w是行程timer是重复间隔（我们假设 f < r，但如果需要，这可以修复）对于每个顶点，我们将（如正常的 Dijkstra 中一样）维护至少两个值：首先，我们将记住我们是否已经处理了该顶点。其次，我们将维护该位置当前已知的最早到达时间，包括最后一条用于获取该潜在到达时间的边的信息。对于起点，最早到达时间最初是期望的出发时间，对于所有其他顶点，初始到达时间是无穷大。
然后 Dijkstra 可以正常进行：贪婪地选择到达时间最早的未处理顶点，例如到达时间为 t 的顶点
u。然后处理这个顶点：对于它的每个出边，计算可能到达目标顶点v的最早时间：t' = t + ((r + f - (t % r)) % r) + w（想一想；如果f >= (t % r)，则f - (t % r)是等待时间）。如果t'小于或等于v已知的到达时间，则将v的到达时间设置为t'并将该边添加到可能的源边集合中以获得该到达时间（如果它严格较小，则首先删除所有其他边）。在这里尝试一下：https://open.kattis.com/problems/shortestpath2
It is indeed possible to modify Dijkstra to find the quickest route from station A to station B, also taking into account the departure time and required waiting at intermediate stations. It is not, as the other answer claims, NP-complete. In the following, I'm going to assume the bus schedule is periodic (ie. repeats indefinitely), but it should actually suffice to, for each time of day, for each bus stop and for and each line (journey) visiting the bus stop, quickly find the next departure (journey instance).
We model the problem as a directed multigraph: The bus stops are vertices of my graph, and an edge in my graph is a trip from one bus stop to another by some bus line. An edge is formally a tuple
(u_a, u_b, id, f, w, r)whereuis the source vertexvis the destination vertexidis the journey id (needed to retrieve an actual solution - left as an exercise)fis the first departure timewis the travel timeris the repeat interval (We assume f < r, but this can be fixed if needed)For each vertex, we will (as in normal Dijkstra), maintain at least two values: Firstly, we will remember whether we have processed this vertex yet or not. Secondly, we will maintain the earliest currently known arrival time for this location, including information about which edge was the last one used to obtain this potential arrival time. For the startpoint, the earliest arrival time is initially the desired departure time, and for all other vertices the initial arrival time is infinity.
Dijkstra may then proceed as normal: Greedily pick the unprocessed vertex with the earliest arrival time, say vertex
uwith arrival timet. Then process this vertex: For each of its out-edges, calculate the earliest time it is possible to reach the destination vertexv:t' = t + ((r + f - (t % r)) % r) + w(think about it; iff >= (t % r), thenf - (t % r)is the waiting time). Ift'is smaller than or equal to the arrival time already known forv, set the arrival time ofvtot'and add this edge to the set of possible source edges to obtain this arrival time (if it was strictly smaller, delete all others first).Try it out in practice here: https://open.kattis.com/problems/shortestpath2