python - networkx：边缘权重作为计算值

Question

我想用 NetworkX 库实现最短路径算法。就我而言，我的权重函数从其他边缘属性中得出值。因为重量是一个计算值，我不想将它存储为一个额外的属性以避免复杂性，例如在其他属性更改时更新值。然而，NetworkX 的算法 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方法中编写更新代码，但这样做的好处是您不必担心在依赖属性发生更改时更新具体值。相反，您只在被要求时才计算它。

如果您担心许多访问会z导致不必要的潜在昂贵计算，那么将此示例扩展到缓存值将很容易。getter 在进行计算之前会检查查找表。这只是记忆。