BFS

from collections import deque as dq

def directedBFS(digraph, start, end, maxTotalDist, maxDistOutdoors):

    def update_distances_dict(path):
        if distances.has_key(path):
            return distances[path]  # path already memorized
        t, o = 0, 0
        while len(path) > 1:
            original_path = path[:]
            bit = path[-1]
            path = path[:-1]
            if distances.has_key((bit, path[-1])):
                a, b = distances[(bit, path[-1])]
            elif distances.has_key((path[-1], bit)):
                a, b = distances[(path[-1], bit)]
            else:
                a, b = maxDist, maxDist
            t += a
            o += b
            if distances.has_key(path):
                a, b = distances[path]
                t += a
                o += b
                distances[original_path] = (t, o)
                break
        return t, o

    start = Node(start)
    end = Node(end)
    q = dq([[start]])
    #import ipdb; ipdb.set_trace()  # XXX BREAKPOINT
    path = [[start, -1, 0, 0]]  # list of lists, node, dist, odist, child number
    lpath = set([start])  # use set instead of list for in comparison (faster)
    spath = []  # list of nodes for current shortest path
    td, od, finished = 0, 0, 0
    distances = {}  # dictionary for td and od values (faster access)
    # this dictionary will store td and od with keys = path effectively
    # memoizing the distance lookup element of the BFS
    maxDist = 0
    for n_dict in digraph.edges.iteritems():
        for n_list in n_dict:
            if isinstance(n_list, list):
                for e_list in n_list:
                    twodistances = (float(e_list[1][0]), float(e_list[1][1]))
                    distances[(n_dict[0], e_list[0])] = twodistances
                    maxDist += twodistances[0]
    tdspath = maxDist; odspath = maxDist

    while len(q) != 0:
        tmpPath = q.popleft()
        lastNode = tmpPath[len(tmpPath) - 1]
        td, od = update_distances_dict(tuple(tmpPath))
        if td <= tdspath and td <= maxTotalDist and od <= maxDistOutdoors:
            if lastNode == end:
                # calc length and add to dict distances
                # update best tdspath and spath if better
                # don't add back to q, wait to fall out the end
                #return tmpPath
                if td < tdspath:
                    tdspath = td
                    spath = tmpPath[:]
                    odspath = od
            else:
                for linkNode in digraph.childrenOf(lastNode):
                    if linkNode not in tmpPath:
                        newPath = tmpPath + [linkNode]
                        q.append(newPath)
    if spath != [start] and spath:
        return [str(i) for i in spath]
    else:
        raise ValueError('No such path!')