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 に答える