Redis:实现加权有向图

Question

使用Redis实现加权图的最佳方法是什么？

我们将主要搜索图上的最短路径(可能使用Dijkstra算法)

目前我们考虑将边缘添加到Redis

对于每个节点,我们将nodeId作为键和引用节点的键的有序集,sortedSet中每个nodeId的得分是边的权重.

你怎么看？如果我错了,请纠正我,但这里唯一的失败是,对于排序集中下一个节点的每个查询,我们支付O(logn)而不是O(1)...

http://redis.io/commands/zrange

Answer 1

如果一次取出一个有序集合中的下一个项目，那么获取下一个项目的时间复杂度仅为 O(log(n))，在这种情况下，与 Redis 连接的延迟将比操作的复杂性更成为问题。

对于图上的大多数操作，您需要查看节点的所有边，因此在处理节点时将整个集合（或至少具有合适分数的集合）加载到本地内存中是有意义的。这当然意味着加载一些不会被遵循的边，因为您已经找到了合适的路径，但由于集合相当小，因此这样做的成本将远远低于为您所做的每个边对 redis 进行新的调用需要。