Redis：實現加權定向圖

使用Redis實現加權圖的最佳方式是什麼？Redis：實現加權定向圖

我們將主要在圖形上搜索最短路徑（可能使用Dijkstra算法）

目前，我們認爲增加的邊緣，Redis的

對於每個節點，我們將有節點ID爲關鍵以及被引用節點的鍵集的排序集合，sortedSet中的每個nodeId的分數是邊的權重。

您認爲如何？糾正我，如果我錯了，但這裏唯一令人失望的是，對於每個查詢在一個SortedSet的下一個節點，我們付出O（LOGN）而不是O（1）...

http://redis.io/commands/zrange

來源

2011-06-18 DuduAlul

獲得下如果您一次只有一個，那麼排序集中的項只有O（log（n）），在這種情況下，連接到redis的延遲比操作的複雜性更成問題。

對於圖上的大多數操作，您需要查看節點的所有邊，因此在處理節點時將整個集（或至少具有合適分數的）加載到本地內存是有意義的。這當然意味着加載一些不會被遵循的邊緣，因爲你已經找到了合適的路徑，但是因爲這些集合相當小，所以它的成本將遠遠低於你爲每一個邊緣對redis進行新的調用需要。

來源

2011-06-19 00:50:14

對不起，遲到了:)，但我最近遇到了同樣的問題，我用哈希模型。我和湯姆克拉克森同意（幾乎）一切都應該被加載到本地內存和我說，在空間方面的有效方式是使用散列和存儲你這樣的圖形信息，從而增強：

Graph = { node1 : { nodeX : edge_weight, nodeY : edge_weight, other_info: bla..}, 
      node2 : { nodeZ : edge_weight, nodeE : edge_weight, other_info: bla..}, 
      bla bla... 
     }

如果您需要更多的空間和效率，壓縮每個值（可以是JSON字符串...）並在您的客戶端代碼中解壓縮/導入/反序列化。

來源

2011-09-11 12:10:26 hymloth

Redis：實現加權定向圖

回答

相關問題