1

假设我有一个有 100k 节点和 500k 边的有向图。其中 15k 个节点是“重要的”。我需要从一个特定节点开始找到 100 个最近的“重要”节点。

我在 C# 中实现了 Dijkstra 算法，它可以找到从起始节点到所有其他节点的距离。然后我按距离对“重要”节点进行排序并首先返回 100。这大约需要 1 秒钟。

现在我需要在服务器端（Linux）做同样的事情，可能有很多并发查询和不同的起始节点。我尝试过 node4j 图形数据库，在与开发人员协商后，我们得到了在 10-20 秒内完成相同操作的解决方案（实际上，如果我们计算没有长度限制的路径，大约需要 10 分钟）。这需要很长时间，因为 neo4j 存储所有最短路径，而我的 C# 实现只存储距离。在 neo4j 中使其更快的唯一选择是编写扩展，这不是微不足道的。

所以问题是：是否有任何图形数据库（非商业）可以安装在 Linux 服务器上并且能够快速运行这样的查询？我检查了维基百科列表中的所有图形数据库，但没有找到合适的。

另一种选择是在 Java 中实现相同的算法并创建一个服务（Tomcat？），它将存储图的共享副本（如何？）并回答这些查询。但我更喜欢准备好的东西...

4

2 回答 2

2

编写一个 Neo4j 扩展来做到这一点并不像你想象的那么糟糕。

见这里的例子： http: //maxdemarzi.com/2012/11/26/extending-neo4j/

这个使用 A* 算法进行“自定义”寻路：http: //maxdemarzi.com/2012/11/27/pathfinding-with-neo4j-unmanaged-extensions/

于 2013-03-28T04:47:02.670 回答
1

这是对@MaxDeMarzi给出的答案的补充......

您提到您的 C# 实现：（1）查找从起始节点到所有其他节点的距离，（ 2）按距离排序“重要”节点，（3）首先返回 100。

为了提高效率，你可以做这样的事情吗？

top = 100

然后，每次 Dijkstra 找到到新节点的最短路径时：

if (isImportant(node)) resultSet.add(node,distance)
if (resultSet.size() >= top) return resultSet

这将避免找到您不感兴趣的节点的路径

于 2013-03-28T10:26:36.730 回答