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。