在Python的Bellman-Ford实现中使用范围和字典

Question

贝尔曼-福特算法如下所示

initialize-single-source(G,s)
for i = 1 to |G.V| - 1
   for each edge (u,v) in G.E
      call Relax(u,v,w)

and so on

这个伪代码索引从1开始，而不是0。

这就是我所说的边缘。我使用字典来表示边和顶点。

    for i in range((len(self.V.keys()))-1):
        for vertex in self.V.keys():
            for edge in self.V[vertex]:

Q1:我们应该从索引0开始，对吗？

Q2:我们还应该从G.V的长度中减去1吗？

谢谢。

Answer 1

你已经试过this super website了吗？有时答案可以在那里找到……

Answer 2

Q1:我们应该从索引0开始，对吧？

不一定；您也可以遍历xrange(1, len(self.V))。不过，从零开始是惯用的做法。

Q2:我们还应该从G.V的长度中减去1吗？

如果你从零开始计数，是的。-1是算法规范的一部分。

额外建议:将您的代码段重写为

for i in xrange(len(self.V) - 1):
    for vertex in self.V.iterkeys():
        for edge in self.V[vertex]:

要防止构建密钥列表(两次)，请执行以下操作。