networkx：邊緣權重作爲計算值

Question

我想用NetworkX庫實現最短路徑算法。在我的情況下，我的權重函數從其他邊緣屬性導出值。因爲weight是一個計算值，所以我不想將它作爲一個額外的屬性來存儲，以避免複雜性，例如當其他屬性改變時更新該值。然而，NetworkX的algorithm API似乎要求權重是邊緣數據密鑰。

所以我想知道是否有可能不存儲的價值？我的理想情況是爲算法指定一個自定義權重函數。

Answer 1

該參數確實需要是邊緣屬性字典中的關鍵字。因此，您需要在字典中設置邊緣屬性以用作權重。您可以在計算最短路徑之前以簡單的循環方式指定這些路徑（如果需要，稍後再刪除它們）。

或者，您可以修改Dijkstra算法代碼以從其他邊屬性計算您的權重。假設你有一個圖（不是多圖），它是一個單行的變化。把你的體重公式線231 https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/shortest_paths/weighted.py#L231

vw_dist = dist[v] + edgedata.get(weight,1) 

Answer 2

您可以使用屬性懶懶地計算權重值，但將它顯示爲屬性。例如：

class Edge(object): 

    def __init__(self, x, y): 
     self.x = x 
     self.y = y 

    def get_z(self): 
     return self.x + self.y 

    z = property(get_z) 


e = Edge(3,4) 
print e.z 

這裏e.z似乎是一個實際的存儲值時，Edge對象的屬性。但事實並非如此 - 它是按需求計算的。您仍然必須在get_z方法中編寫更新代碼，但是這樣做的好處是，無論何時從屬屬性發生更改時，您都不必擔心更新具體值。相反，只有在需要時才計算。

如果您擔心導致不必要的潛在昂貴計算的許多訪問，可能很容易將此示例擴展到緩存值。在進行計算之前，getter會檢查查找表。這只是memoization。