使用从数据库中提取的数据计算最短路径

所以我需要创建一个Web服务,它将与我的Android进行通信 应用。在我的android应用程序中,客户端选择两点开始和 到达这两点将发送到我的网络服务找到巴士 它们之间有最短的路径。我在网路上遇到问题 服务方面。

我试图用Dijkstra的算法找到两者之间的最短路径 两点。为了测试Dijkstra算法,我必须从a中提取数据 MySQL数据库,并没有把它放进我的算法。我不知道 我怎么能这样做。

在我的数据库中,我有两张包含公交路线(公交车号)的表格, 代码(站号),pt_arret(站名)。还有另一张桌子 包含位置代码(id站),经度和纬度,以及 距离(是车站和车站之间的距离 之前。

0
额外 编辑
意见: 1
(对不起拼写错误,因为我不会说流利的英语)
额外 作者 olfa,
请你花时间格式化,大写并恰当地标点你的问题。谢谢。
额外 作者 NPE,

1 答案

你必须创建一个可以让你使用Dijkstra算法的结构。为此,您必须从数据库中读取所有相关数据。从关系数据到面向对象的转换总是很笨拙。

理想情况下,您希望每个表使用一个简单的SQL选择来获取数据。优化是棘手的。一条select语句可以抓取一百万行,几乎可以抓取一行;一个选择会得到一百万行比10选择将获得10行(以我的经验)。但是,如果数据库连接速度较慢(带宽较窄),则抓取太多不必要的行可能需要很长时间。

使用Maps(TreeMap或HashMap)跟踪您读取的内容,以便您可以找到已经读取并放置在结构中的“工作站”对象,并为它们添加连接。

一旦将数据结构设置在内存中,尽量保持它在最短的时间内,以限制重新读取数据库的延迟。

留意你的记忆和时间。您的用户运行速度太慢或内存不足。你需要关注性能(这些日子似乎并不是一种常见的需求)。我提出了一些建议,但我无法真正了解您的硬件和数据会发生什么。 (例如,阅读数据库可能不如我怀疑的那么慢。)

希望这可以帮助。如果你以前没有做过这样的事情,你就有很多工作和学习。我在这样一个主要的程序上工作(但是它也给DB写了一个),我觉得我一直在上游游泳。

增加:</强>

你在内存中想要的是一组站(站类对象)和路由(路由类对象)。每个工作站都将拥有描述一个工作站(包括位置)所需的全部数据。重要的是,它也需要一个ID。电台应该使用ID作为密钥进入TreeMap。 (这是我的偏见,很多人会使用HashMap。)

每条路线都会提及它所链接的两个电台,距离或旅行时间以及其他所需信息。

每个电台 也会包含引用它的路由列表。我建议使用LinkedList来获得灵活性。 (在这种情况下,ArrayList容易浪费大量的空间而不使用数组元素。)您将需要从数据库中读取站点,然后读取路由信息。在您读取每条路线的信息时,请创建路线对象,找到两个车站,将它们的引用添加到路线,然后将路线添加到两个车站的路线列表中。

现在,每个车站都可以看到所有的路线,然后通过一次公交车就可以找到所有车站。从这些站点,您可以通过您的网络工作。如果你想这样想,这个结构真的是一个“稀疏阵列”。

应用Dijkstra算法 - 或者任何其他算法 - 非常简单。您需要站点和路线上的各种标记(站点和路线类别中的字段)来跟踪您已用于各种目的的节点(站点)和连接(路线)。它可能有助于在一张纸上绘制地图(从一个小图开始!)以跟踪您的代码正在做什么。我的经验是,所有这些都需要很少的代码,但需要仔细考虑。

0
额外
我很抱歉,但我想知道:创建这个ws什么是我需要的类和函数。因为这是我的第一个ws,我不知道如何分析这个问题。
额外 作者 olfa,
有人建议我这样做:
额外 作者 olfa,
有人建议我这样做:要使用Dijkstra算法,你需要准备一个距离矩阵。它是所有站点之间的二维距离阵列。优先解决方案是:1.将两个表格作为POCO数据对象加载到内存中。 2.计算距离矩阵(如果可以的话 - 创建一个sparce矩阵以避免内存使用量过大)。 3.调用Dijkstra的算法....所以应该从哪里提取数据(在这个类中)?我很抱歉,但我需要帮助:(
额外 作者 olfa,
非常感谢你的建议:)我会尝试将它翻译成代码,但请如果你知道一个教程,可以帮助我不要吝啬给我的网址,因为我是初学者,我不知道如果我可以从头开始构建它。无论如何,我会尝试再次感谢你:)
额外 作者 olfa,
非常感谢你的帮助:)我希望我尽快找到一个解决方案,因为我在11天后失去了大量的研究和报告:( :(再次感谢你:)
额外 作者 olfa,
@olfa:你需要哪些方面的帮助?我不知道Web服务和Android足以帮助你。我可以更具体一些关于SQL,Java和实现Dijkstra的算法。
额外 作者 RalphChapin,
@olfa:对不起,但我不了解你。
额外 作者 RalphChapin,
@olfa:合理的建议。我已经将我的解释加入了我的答案。应该让你更进一步。
额外 作者 RalphChapin,