一尘不染

Redis:实现加权有向图

redis

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

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

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

对于每个节点,我们将使用nodeId作为键,并使用引用节点的键的sortedset,sortedSet中每个nodeId的分数就是边缘的权重。

你怎么看?如果我错了,请纠正我,但这里唯一的遗憾是,对于sortedset中的下一个节点的每个查询,我们支付O(logn)而不是O(1)…

http://redis.io/commands/zrange


阅读 525

收藏
2020-06-20

共1个答案

一尘不染

如果您一次取出一个排序集中的下一个项目,则仅获得O(log(n)),在这种情况下,与redis的连接延迟将比操作的复杂性更成问题。

对于图形上的大多数操作,您需要查看节点上的所有边,因此在处理节点时,将整个集合(或至少具有适当分数的那些)加载到本地内存中是有意义的。当然,这将意味着加载一些不会遵循的边缘,因为您已经找到了一条合适的路径,但是由于这些集合很小,因此这样做的代价将远远小于对您所做的每个边缘重新调用redis需要。

2020-06-20