我的目标是为道路网络编写最短路径算法。
目前我的架构是这样的:我将所有数据存储在支持 PostGIS 的 PostgreSQL 数据库中。我做了一个 SELECT * FROM ways，它在一个有 100,000 个边(路)的表上用了不到 3 秒，然后我将应用一个(Java、Ruby 或任何基于任何东西的)最短路径算法来已经驻留在内存中的图形。在具有 100,000 个边的图形上，第二个操作可能需要大约 1.5 秒。
所以，需要:
- 2-3 秒将数据库中的所有路径加载到内存中并创建一个图(节点存储在一个表中并带有路径(边))；
- 1-1.5 秒计算已在内存中的图上的最短路径。
这与 pgRouting 所做的非常相似(据我所知，它使用 C Boost 将图形存储在内存中)，除了 pgRouting 总共需要大约 2 秒来计算同一数据集上的最短路径(是的，它是很快，但它对我来说是一个黑盒子，所以我需要自己的)。
但最近我发现了有关图形数据库和 Neo4j 的信息。在他们的网站上，他们声称“仍然能够在数百万条道路和航路点的图表上以亚秒级的速度进行这些计算，这使得在许多情况下可以放弃使用 K/V 存储预先计算索引的正常方法，并且能够将路由置于关键路径中，以适应生活条件并构建高度个性化和动态的空间服务。”。
所以问题是:对于我的特定问题，图形数据库会更快吗？
问题具有以下性质:
- 数据库由一个表(ways)组成；
- 对数据库的唯一查询是将所有路径获取到内存中(构建图形)；
- 我不需要可扩展性，即图很可能不会增长。
最佳答案
如果您使用任何图形数据库(例如 Neo4j)，您当然不必重新发明轮子。其中内置了许多最短路径算法，它旨在处理复杂性，以防您必须考虑任何特定道路、单向道路、道路得分等的速度限制。当数据增长时，您如何跟上性能 10次，或者说，100 次。考虑到 100,000 种方式的总计算时间为 3 秒，1M 种方式可能需要几分钟，而在 Neo4j 中，响应将以毫秒为单位。
关于database - 图数据库更适合最短路径算法吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6897546/