networkx: 边权重作为计算值

Question

我想用NetworkX库来实现一个最短路径算法。在我的情况下，我的权重函数是根据其他边的属性来计算的。因为权重是一个计算出来的值，我不想把它作为额外的属性存储，这样会增加复杂性，比如当其他属性改变时还得更新这个值。不过，NetworkX的算法接口似乎要求权重必须是边数据的一个键。

所以我在想，是否可以不存储这个值？我理想的情况是能够给算法指定一个自定义的权重函数。

Answer 1

你可以懒惰地计算权重值，但看起来就像它是一个属性，使用属性来实现。例如：

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会导致不必要的、可能昂贵的计算，这个例子很容易扩展来缓存值。获取器会在进行计算之前检查一个查找表。这就是所谓的记忆化。

Answer 2

这个参数确实需要是边属性字典中的一个键。所以你需要在字典里设置一个边的属性来用作权重。在计算最短路径之前，你可以在一个简单的循环中给这些属性赋值（如果需要的话，之后可以删除它们）。

另外，你也可以修改Dijkstra算法的代码，从其他边属性中计算你的权重。假设你有一个图（不是多重图），这只需要一行代码的修改。把你的权重公式放在第231行。

https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/shortest_paths/weighted.py#L231

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