Using range and dictionary in Python's Bellman-Ford implementation

The Bellman-Ford algorithm looks like this

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

This psuedocode index begins with 1, not zero.

Here is how I called the edge. I use dictionary for edge and vertex.

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

Q1: We should begin with index zero, right?

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

Thanks.

Answers


Did you already give this super website a try? Sometimes answers can be found there...


Q1: We should begin with index zero, right?

Not necessarily; you could also iterate over xrange(1, len(self.V)). Starting from zero is idiomatic, though.

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

If you start counting from zero, yes. The -1 is part of the algorithm specification.

Extra advice: rewrite your snippet as

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

to prevent building a list of keys (twice).


Need Your Help

SIP: IPSEC vs TLS

ssl sip voip ipsec

I am new to the VOIP concepts. I just took a course on VOIP. I am interested in implementations of SIP using TLS, IPSEC and Digest as well.

Is CSS3's 'move-to'/content: pending(…) supported in any browsers?

html css html5 css3

"How do I re-order elements using pure CSS" is a commonly asked question. And you have to use Javascript for it.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.