c# - 使用 Dijkstra 算法实现时间表

Question

我正在尝试实现一个阅读教练时间表的系统来计划旅程。

这是我的场景:
我只想输入旅行日期、起点站和终点站，但从 A 到 B 可能涉及 3 或 4 个转接旅程，我想返回几个选项，按总数排序所需时间。我的数据库设置有一个车站表、一个旅程表和一个旅程实例表(即包含旅程运行日期)。

我在 Dijkstra 算法的 C# 中得到了很好的实现，但我发现它是有限的，因为我不知道如何包括在公交车站等待转接旅程的时间，而且事实上许多旅程可以从在不同的时间从一个车站到另一个车站更增加了困惑。我还必须考虑旅程是否需要一天甚至两天才能完成，事实证明这很麻烦。 Dijkstra 值得在这里坚持下去吗？或者有人知道其他可能更适合的东西吗？

我正在使用 asp.net MVC3、C# 和 EF4，但我在这里追求的并不是太多代码 - 更多只是我最好使用的流程的正确方向上的一点，因为这很好超越我以前做过的任何事情。 (当我自愿参与这个项目时，我可能贪得无厌!)如果有人可以提供一些建议，或者一些可以帮助解决这种情况的文档的链接，那将有很大帮助。谢谢

Answer 1

首先:感谢您自愿参与一个雄心勃勃的项目。其次:这可能有点具有挑战性，从下面链接的另一篇 StackOverflow 帖子来看:NP-Complete。

Dijkstra 算法在静态图上找到单源最短路径，但这不是您在这个问题中所做的。由于此类图中的顶点可能存在于重叠的时间空间中，因此从 a₁ 到 a₂ 最快的巴士可能会在中午 12:00 出发，但最快的巴士a₂ 至 a₃ 可能于当天上午 11:59 出发。这是不可能的。

显然，你已经考虑过这一点，但看待问题的抽象方式是，你并不是试图找到图中的最短路径，而是试图找到图中的最短路径。有效地三维空间(时间作为第三维)。假设您根据时间对节点进行拓扑排序，则可以将强力方法(对于小图来说仍然很好)实现为广度优先搜索。

相关链接在这里:Bus public transport algorithm

有关该主题的一些阅读:

• http://web.archive.org/web/20121224231948/http://www2.isye.gatech.edu/~mwps/publications/archetti-savelsbergh-revision.pdf
• http://digbib.ubka.uni-karlsruhe.de/volltexte/documents/2792

愿原力与你同在。