Проблемы с «посещенным списком» при использовании Dijkstras, Python

Question

Я относительно новичок в кодировании, поэтому извиняюсь за переписанный, неуклюжий код.

Дополнительно ф.р. это из Открытого курса MIT "Задача 11, Самый быстрый способ обойти MIT". (Для более поздних наборов проблем я не могу найти решения онлайн ..)

Я реализовал наиболее успешную версию алгоритма Дейкстры с динамическим программированием и без него. В этой реализации я веду список узлов, чтобы избежать циклов / бесконечных циклов ... Но, насколько я понимаю, я столкнулся с этой проблемой. Учитывая, что мои ребра взвешены, и в некоторых случаях я хотел бы вернуться к тем же узлам через разные EDGES, это приводит к тому, что мой код игнорирует правильные решения. Поэтому я хотел бы найти способ изменить свой код так, чтобы он запоминал, какие ребра были посещены, а не какой узел и ... Я действительно пытался изменить его, чтобы запомнить, к каким ребрам обращались, - но моя реализация не сработала - так что я хотел бы увидеть правильный способ написать это.

Пример ввода, в котором мой код не выполняется:

# Test case 6
print "---------------"
print "Test case 6:"
print "Find the shortest-path from Building 1 to 32 without going outdoors"
expectedPath6 = ['1', '3', '10', '4', '12', '24', '34', '36', '32']
brutePath6 = bruteForceSearch(digraph, '1', '32', LARGE_DIST, 0)
dfsPath6 = directedDFS(digraph, '1', '32', LARGE_DIST, 0)
print "Expected: ", expectedPath6
print "Brute-force: ", brutePath6
print "DFS: ", dfsPath6

И вывод этого кода ...

---------------
Test case 6:
Find the shortest-path from Building 1 to 32 without going outdoors
Expected:  ['1', '3', '10', '4', '12', '24', '34', '36', '32']
Brute-force:  ['1', '3', '10', '13', '24', '34', '36', '32']
DFS:  ['1', '3', '3', '3', '7', '7', '9', '13', '24', '34', '36', '36', '32']

Список смежности представлен в форме дикта внутри диктанта, где веса хранятся в виде кортежа. Для проверки кода перебора, ввода карты или построения орграфа перейдите на этот GitHub здесь .

def findDist(digraph, start, path):
path = [str(start)] + path
distance = 0
outDistance = 0
for i in range(len(path)-1):
    edgeVals = None
    listOfDest = digraph.edges[Node(path[i])]
    for node in listOfDest:
        if node.has_key(Node(path[i+1])):
            edgeVals = node.values()
            distance = distance + edgeVals[0][0]
            outDistance = outDistance + edgeVals[0][1]
            break
return (distance, outDistance)

def directedDFS(digraph, start, end, maxTotalDist, maxDistOutdoors, toPrint = False, visited = [], level = 0, memo = {}):
"""
Finds the shortest path from start to end using directed depth-first.
search approach. The total distance travelled on the path must not
exceed maxTotalDist, and the distance spent outdoor on this path must
not exceed maxDisOutdoors.

Parameters: 
    digraph: instance of class Digraph or its subclass
    start, end: start & end building numbers (strings)
    maxTotalDist : maximum total distance on a path (integer)
    maxDistOutdoors: maximum distance spent outdoors on a path (integer)

Assumes:
    start and end are numbers for existing buildings in graph

Returns:
    The shortest-path from start to end, represented by 
    a list of building numbers (in strings), [n_1, n_2, ..., n_k], 
    where there exists an edge from n_i to n_(i+1) in digraph, 
    for all 1 <= i < k.

    If there exists no path that satisfies maxTotalDist and
    maxDistOutdoors constraints, then raises a ValueError.
"""
#TODO
if toPrint:
    print start, end
check = start
start = Node(start)
end = Node(end)
if not (digraph.hasNode(start) and digraph.hasNode(end)):
    raise ValueError('Start or end not in graph.')
path = [str(start)]
if start == end:
    return path
shortestDist = None
shortestOutDist = None
distFilter = (maxTotalDist <= maxDistOutdoors)
for child in digraph.childrenOf(start):
    childNode = child.keys()[0]
    if (str(childNode) not in visited):
        visited = visited + [str(childNode)]
        try:
            newPath = memo[start, end]
        except:
            newPath = directedDFS(digraph, str(childNode), str(end), maxTotalDist, maxDistOutdoors, toPrint, visited, level = level + 1)
        if newPath == None:
            continue
        newPathDist = findDist(digraph, start, newPath)
        if (distFilter) and (newPathDist[1] <= maxDistOutdoors) and ((shortestDist == None) or (newPathDist[0] < findDist(digraph, start, shortestDist)[0])):
            shortestDist = newPath
        elif (not distFilter) and ((shortestOutDist == None) or (newPathDist[1] <= findDist(digraph, start, shortestOutDist)[1])):
            if (shortestOutDist == None) or (newPathDist[0] <= findDist(digraph, start, shortestOutDist)[0]):
                shortestOutDist = newPath
                memo[childNode, end] = newPath
if (distFilter) and (shortestDist != None):
    path = path + shortestDist
elif (not distFilter) and (shortestOutDist != None):
    path = path + shortestOutDist
else: 
    path = None
if (level == 0) and (not distFilter) and (shortestOutDist == None):
    raise ValueError('No such path!')
elif (level == 0) and (not distFilter) and (findDist(digraph, start, shortestOutDist)[1] > maxDistOutdoors):
    raise ValueError('No such path!')
elif (level == 0) and (distFilter) and (shortestDist == None):
    raise ValueError('No such path!')
elif (level == 0) and (distFilter) and (findDist(digraph, start, shortestDist)[0] > maxTotalDist):
    raise ValueError('No such path!')
return path

Прикреплено изображение ожидаемого результата по сравнению с фактическим - игнорируйте последние два, поскольку это уже решено. Вы можете увидеть тестовые примеры 4 и 6 с проблемами. Результат кода

Спасибо!