Finding the closest node
def search(graph, node, maxdepth = 10, depth = 0):
    nodes = []
    for neighbor in graph.neighbors_iter(node):
        if graph.node[neighbor].get('station', False):
            return neighbor
        nodes.append(neighbor)


Why store the neighbor in the list? Instead of putting it in a list, just combine your two loops.

for i in nodes:


i typically stands for index. I suggest using neighbor to make your code easier to follow

    if depth+1 &gt; maxdepth:
        return False


This doesn't relate to this individual node.  What is it doing inside this loop?

        if search(graph, i, maxdepth, depth+1):
            return i
   return False


Failure to find is better reported using None rather than False.