Problem of rewriting Python code in C

[Fernando Pereira]

On 5/27/02 2:18 AM, in article
mailman.1022480443.1123.python-list at python.org, "Dave Lin"
<ddmanlin at mail2000.com.tw> wrote:

>   I use Python to implement a math optimization problem, and I found 1 of my
> function is bottleneck (dijkstra algorithm, if you want to know), I tried to
> rewrite the function in C, but after I profiled it, the result is even
> slower!? I guess that's because I use a lot of python elements in C code, ex.
> PyList, PyDict, even third party module, ex. kjbucket, pqueue, etc. Am I
> right? If that's the problem, what should I do?
Before you spend more time on a C reimplementation, there are a few
questions about your Python implementation:

1. What's the purpose of seenLinks? If your graph has no negative-weight
loops (a required property for Dijkstra's algorithm), a correct
implementation of the algorithm visits any edge (link) reachable from the
source exactly once, without needing your seenLinks test. A common bug in
implementations of the algorithm is to forget to update the position in the
queue of a relaxed node. Looking at your code, I'm not sure that you are
doing update correctly. Bugs like that, which destroy the algorithm's main
invariant, can cause edges to be visited more than once, leading to
pseudo-fixes like the one of keeping a visited edge table, which don't
really do the right thing (they fail to find the shortest path in some
cases).

2. You seem to use maps indexed by pairs for several purposes, including the
graph edges. That's probably less efficient than an adjacency list
representation.

You might want to look at

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466

It implements the algorithm with an appropriate queue data structure, and it
is very simple

-- F