找到參數內的最短圖形

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的最小路徑。找到參數內的最短圖形

我已經試過打印語句，我即將放棄。我只是不明白爲什麼它現在不正確。

來源

2011-05-07 Glassjawed

我不知道爲什麼你的代碼結果不正確。但是，您是否意識到這是非常低效的？它看起來像我正在搜索每個可能的非循環路徑，從起始節點開始尋找最短路徑。有更快的方法來做事情。 – 2011-05-07 01:21:45

我知道，但我不知道如何編寫這樣的方法。但是，這讓我感到莫名其妙，爲什麼我的if語句拋出了一些結果。 – Glassjawed 2011-05-07 02:28:04

對於簡單的最短路徑函數，請查看http://www.python.org/doc/essays/graphs/。可能有幫助。 – 2011-05-07 15:09:58

由於您使用的算法（DFS）沒有返回最短路徑，因此您的代碼不會返回可能的最短路徑。相反，請嘗試BFS！

但是，由於您有一些體重限制（室外距離），您應該檢查出Dijkstra's shortest path algorithm。你應該覺得很容易整合你的約束條件。

來源

2011-06-17 03:28:54

找到參數內的最短圖形

回答

相關問題