公交数据库设计与算法？

Question

我们想要实现Android的公共交通指南。输入将是起点和目标点。输出将是告诉如何使用公交车、地铁等到达目的地的指令。e.c这对于大城市来说并不容易，我们必须有一个设计良好的数据库来快速回答。运输算法必须给乘客提供最优线路。我想看看你在数据库和算法设计方面的宝贵想法。非常感谢你的回答。

Answer 1

最有可能的情况是，你需要一个graph来计算最短路径。

您的图形将是G=(V,E)，以便V = {all possible stations}和E = {(u,v) | there is a transport connecting station u to station v}。

如果你的图表不能放入内存中，这可能是一个大城市的情况，你可能想要创建一个函数successors(u) = { v | (u,v) in E }，它将允许你在飞行中计算图表。

在this older question中，有一些关于如何有效地在动态环境中找到两个顶点之间的路径的讨论，类似于您正在描述的环境。