Problem of rewriting Python code in C

[Dave Lin]

Dear Sir,
    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?

the code in Python:

def Dijkstra(start, end, nodes, links, graph, maxDistance, nodeNum, linkNum):

    # implicit self-loop == path of length 0
    if start == end:
       return (0, {}, [start])

    # priority queue of path costs from start with edges
    Q = pqueue.create(nodeNum)

    #set S
    seenLinks = kjbuckets.kjSet(linkNum)

    #for KEDSP update, travled nodes in algorithm
    seenNodes = [start]

    #initial nodes
    for node in nodes:
        node.distance = maxDistance
        node.preceding = None

    start.distance = 0.0
    #first step: strat node to neighbor
    for neighbor in graph.neighbors(start):
        pair = (start, neighbor)
        link = links[pair]
        Q.push(link.cPI, (link.cPI, pair))
        seenLinks[link] = 1
        
    while Q.peek() != None:
        (distance, pair) = Q.pop()
        # DEBUG PRINT STATEMENT
        #print distance, pair
        (left, right) = pair
        if distance < right.distance:
            seenNodes.append(right)
            right.preceding = left
            right.distance = distance
            if right == end:
                #done!
                selectedLinks = {}
                node = end
                while node.preceding != None:
                    link = links[(node.preceding, node)]
                    selectedLinks[(node.preceding, node)] = link
                    node = node.preceding
                return (distance, selectedLinks, seenNodes)
            #otherwise add new edges
            for neighbor in graph.neighbors(right):
                pair = (right, neighbor)
                link = links[pair]
                if not seenLinks.has_key(link):
                    seenLinks[link] = 1
                    Q.push(link.cPI + distance, (link.cPI + distance, pair))
    raise ValueError, "Dijkstra unreachable"

the code in C is too long, I attach it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20020527/2534de63/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: zd3sub.c
Type: application/octet-stream
Size: 7221 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20020527/2534de63/attachment.obj>