kinow/dijkstras-algorithm — pull request #1 by rbrito (2013-02-21 01:59:53+00:00)
Title: "Fix" (not really) the initialization of Dijkstra's algorithm.

Avoid burning so many cycles with an `if` inside a `for` that will have its `if` part executed only once.

While this does not in any way change the complexity of the algorithm, it will most certainly be cache friendlier this way. (It is also incorrect in that we insert the start node once with the key being "infinity", that is, sys.maxint).

Actually, if we *do* want to have a better initialization of the heap, we should:

* *Not* insert the nodes one by one on the heap (this will have complexity of \Theta(n lg n), where n is the number of vertices in the graph).

* Instead, create the vector of everything that the heap should have in the first place (say, creating a vector, list, whatever) and imposing the heap structrure on it *after* that. This will only take \Theta(n) (i.e., linear) time to initialize (with a call to `heapq.heapify`). This would be something like the following pseudo-code:

[sys.maxint, sys.maxint, ..., 0, ..., sys.maxint, ..., sys.maxint],

with the 0 occuping the position of the start node.

Of course, this will *not* make the algorithm much faster, as the bottleneck in in other places, but should not hurt much if we actually implement this in a not-so-bad way.