使用Dijkstra算法实现时间表

我试图实施阅读教练时间表的系统来规划旅程。使用Dijkstra算法实现时间表

这里是我的场景：
我想要输入一个旅行日期，一个起点站和一个终点站，但是从A到B，可能会有3或4个连接旅程， d喜欢返回几个选项，按照所需的总时间排序。我设立的数据库有一张用于电台的表格，一个旅程表格和一个旅程实例表格（即包含旅程的包含日期）。

我已经在C＃Dijkstra算法中实现了很好的实现，但是我发现它是有限的，因为我无法弄清楚如何在公交车站等待连接旅程的时间，以及许多旅程可以去的事实在不同的时间从一个站到另一个站正在增加混乱。我还必须考虑到旅程需要一天甚至2天才能完成，这已经证明很麻烦。迪杰斯特拉是否值得在这里坚持下去，还是有人知道其他可能更适合的东西？

我正在使用asp.net MVC3，C＃和EF4，但它没有那么多的代码，我在这里后 - 更多只是在我最好使用的过程的正确方向的一个点，因为这是远远超出我之前做过的任何事情。（当我自愿参与这个项目时，我可能会咬掉更多的东西！）如果任何人都可以提供一些建议，或者链接到一些能够帮助解决这种情况的文档，那将会有很大的帮助。谢谢

来源

2012-02-22 e-on

好吧，现在开始更担心，因为它似乎没有其他人知道:) – 2012-02-22 15:21:54

首先：对志愿者进行一项雄心勃勃的项目很有帮助。其次：这可能是一个有点挑战，从另一个StackOverflow帖子链接如下：NP-Complete。

Dijkstra算法找到静态图上的单源最短路径，但这不是你在这个问题中所做的。由于在这样的曲线图的顶点将在重叠时间间隔可能存在，从最快总线到可以在下午12:00，但是从最快总线离开到可于同日上午11:59离开。这是一个非首发。

很显然，你已经想到了这一点，但是看问题的抽象方式是，你不是试图在图中找到最短路径，而是试图找到最短路径是有效的三维空间（时间作为第三维）。蛮力方法（对于小图很好）可以实现为广度优先搜索，假设您根据时间拓扑排序节点。

相关链接是在这里：Bus public transport algorithm

一些阅读的题目

愿原力与你同在。

来源

2012-02-23 00:45:37 Brandon

嗨布兰登 - 非常感谢。目前正在阅读上面添加的SO链接上的多模态路线规划。稍后会回报... – 2012-02-23 10:19:36

使用Dijkstra算法实现时间表

回答

相关问题