mysql - 组合数据以生成图形中的路线。从哪儿开始？

Question

我什至不确定这个问题的标题是否最能反射(reflect)我真正想做的事情，实际的问题内容也很困惑，因为我不确定我真正需要什么，但我指望你伙计们来帮助我。

我正在尝试找出最佳方法，以在航类搜索应用程序上基于简单的直接路线生成更复杂的多路径路线。

假设我的 Routes 表中有两条飞行路线:

Origin              Destination
MIA (Miama)         ATL (Atlanta) and
ATL (Atlanta)       LAX (Los Angeles)

通过这两条路线并发出一个简单的查询，例如:

SELECT ... FROM  Routes WHERE origin = 'MIA' AND destination = 'LAX'

我没有得到任何结果，但如果我能够结合我拥有的所有数据，那么我将能够提供通过 ATL(亚特兰大)的路线:MIA -> ATL -> LAX。

我正在研究 Neo4J 来保存我的数据并使用最短路径执行我的搜索，但我不确定我是否需要这么大的工具。截至目前，我正在使用 MySql，如果我正确地构建我的数据，我想我应该能够做到。

我已经使用 Neo4J ( http://blog.neo4j.org/2013/08/finding-shortest-path-through-park.html ) 研究了最短路径算法，但由于我对此类问题还很陌生，所以我还有其他一些关于如何解决这个问题的问题。

所以我的问题是:

1. 我应该使用我的基本直接路线来预先计算复杂的路线，例如 MIA -> LAX，还是应该使用工具/算法根据我拥有的数据动态生成它？
2. 如果我预先计算复杂的路线，我应该从哪里开始？任何算法提示？这是我最困难的地方。
3. 为此我需要图形数据库还是 MySql 可以？我有大约 35k 不同的基本路线，每秒不超过 10 个请求。
4. 我还想将我的结果限制在距离不超过 3 或 4 条腿的航线上，因为比这更大的航线可能会在非常奇怪和漫长的飞行中连接整个世界

非常感谢

Answer 1

1. 我认为你应该让算法即时计算你的路线，因为它在设计上更灵活，而且当你更新更多数据(在本例中为路线)时，你将不必额外计算和存储复杂的路线
2. 引用1
3. 是的，使用图形数据库，您的查询会更快。如需比较，请在此处查看:here .有很多这样的比较和基准测试和上传，你可以谷歌它。
4. 您可以通过限制密码查询(neo4j 的查询语言)中的跃点数轻松做到这一点

所以在你的情况下，图表会是这样的

(MIA)-[:CONNECTS]->(ATL)-[:CONNECTS]->(LAX)

所以你只需要查询

MATCH p=(f:LOCATION)-[:CONNECTS*1..3]->(g:LOCATION) where f.name = "MIA" and g.name="LAX" return nodes(p) as ConnectingAirports

因此，如果您在 name 属性上索引 LOCATION 节点，这将使您的查询更快。此外，上述查询不仅会为您提供 ATL，还会为您提供所有其他通过 CONNECTS 关系互连并且距离 MIA 1,2 或 3 跳的路由位置 位置。