使用Dijkstras和Python时“访问列表”出现问题

Question

我是一个比较新的编码，所以为覆盖，笨拙的代码道歉。你知道吗

另外，这是麻省理工学院的开放式课件“习题集11，绕过麻省理工学院的最快方法”。（对于以后的问题集，我无法在网上找到解决方案。）

我已经实现了Dijkstra算法的一个最成功的版本，有动态规划和没有动态规划。在这个实现中，为了避免循环/无限循环，我保留了一个节点列表……但据我所知，这就是我遇到问题的地方。考虑到我的边是加权的，并且在某些情况下我希望通过不同的边重新访问相同的节点，这将导致我的代码忽略正确的解决方案。所以我想找到一种方法来修改我的代码，让它记住哪些边被访问过，而不是哪个节点，而且…我确实尝试过修改它来记住哪些边被访问过-但是我的实现不起作用-所以我很想看看正确的写方法。你知道吗

代码失败的输入示例：

# 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']

邻接列表的形式是dict中的dict，其中权重存储为元组。要检查暴力代码、地图输入或有向图的构建方式，请转到GitHubhere。你知道吗

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有问题。Code result

谢谢！你知道吗