0 
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 的最小路径。

我已经尝试过打印语句，我即将放弃。我只是不明白为什么它现在不正确。

4

1 回答 1

1

您的代码不会返回可能的最短路径，因为您使用的算法 ( DFS ) 不会返回最短路径。相反，尝试BFS！

但是，由于您有一些重量限制（户外距离），您应该查看Dijkstra 的最短路径算法。您应该会发现集成约束非常容易。

于 2011-06-17T03:28:54.250 回答