Optimize BFS weighted search in python I have a weighted BFS search in python for networkx that I want to optimize:

def bfs(graph, node, attribute, max = 10000):
    # cProfile shows this taking up the most time. Maybe I could use heapq directly? Or maybe I would get more of a benefit making it multithreaded?
    queue = Queue.PriorityQueue()
    num = 0
    done = set()
    for neighbor, attrs in graph[node].iteritems():
        # The third element is needed because we want to return the ajacent node towards the target, not the target itself.
        queue.put((attrs['weight'], neighbor, neighbor))
    while num &lt;= max and not queue.empty():
        num += 1
        item = queue.get()
        if graph.node[item[1]].get(attribute, False):
            return item[2]
        for neighbor, attrs in graph[item[1]].iteritems():
            if neighbor not in done:
                queue.put((item[0] + attrs['weight'], neighbor, item[2]))
                done.add(neighbor)
Some things that might improve your code:


Use heapq rather than Queue.PriorityQueue. The latter does synchronization stuff that you don't need, so heapq will be faster.
Don't add neighbor to done in your inner loop. This will find incorrect routes on any graphs where some subpath A->B->C is shorter than A->C. Instead, you want to be be putting item[1] into done when you pop it off the queue. Since this means you will get some duplicated nodes in your queue, you'll also need to check if the newly popped node was already done before processing it. You might be able to save a little processing time by storing the cost of the path to the node in a dictionary, and only adding a new path if it's less than the previous one (but I don't think the improvement is very large).
This is a readability improvement (not a performance or correctness fix), but I suggest unpacking item into several values, rather than indexing it. cost, node, first_step = queue.get(), or something similar.
A terminology suggestion: Rather than being a basic breadth-first search, this is Dijkstra's Algorithm. If all the edge weights are equal, you'll examine nodes (roughly) the same order as in a BFS, but if you have different weights you'll go in a different order. It might be a good idea to use a function name that reflect what you're actually doing in the code.