def shortestPath(digraph, start, end, maxTotalDist, maxDistOutdoors, visited=[]):
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
shortest = None
MinimumTotalDist = 0
for node in digraph.childrenOf(start):
if (str(node) not in visited): #avoid cycles
visited = visited + [str(node)] #new list
FirstStepDist = digraph.childrenOf(start)[node][0]
FirstStepOutdoors = digraph.childrenOf(start)[node][1]
newPath = shortestPath(digraph, node, end, maxTotalDist, maxDistOutdoors, visited)
if newPath == None:
continue
TotalDist = int(FirstStepDist) + TotalDistance(digraph,newPath)
TotalOutdoorDist = int(FirstStepOutdoors) + TotalOutdoorDistance(digraph,newPath)
**if TotalOutdoorDist > maxDistOutdoors:
continue**
if (shortest == None or TotalDist < MinimumTotalDist):
shortest = newPath
MinimumTotalDist = TotalDist
if shortest != None:
path = path + shortest
else:
path = None
if TotalDistance(digraph,path) <= maxDistOutdoors:
return path
它没有给我正确的答案。它返回一个有效的路径,是的。但是,它返回的路径并不是最短路径。问题在于粗线,如果它的总室外距离大于约束 maxDistOutdoors,我跳过路径,但我不知道如何更改它。当我删除那条粗线时,我得到了正确的最小路径,但是如果我需要在那里进行这样的检查,因为我想找到总室外距离小于 maxDistOutdoors 的最小路径。
我已经尝试过打印语句,我即将放弃。我只是不明白为什么它现在不正确。