在Python的BellmanFord实现中使用范围和字典

Question

Bellman-Ford算法是这样的

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

此psuedocode索引以1开头，而不是零。在

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

^{pr2}$

问题1：我们应该从指数0开始，对吗？在

问题2：我们还应该从G.V的长度上减去1吗？在

谢谢。在

Answer 1

你已经试过了吗？有时候答案可以在那里找到。。。在

Answer 2

Q1: We should begin with index zero, right?

{cd1>你也不一定能重复。不过，从零开始是习惯用法。在

Q2: Should we still minus 1 from the length of G.V?

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

额外建议：将代码段改写为

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

防止生成键列表（两次）。在