如何在圖上找到滿足約束條件的最短路徑

我試圖在給定約束路徑必須總距離小於某個參數（比方說1000）的加權圖上找到最短路徑。如何在圖上找到滿足約束條件的最短路徑

我試過以下，但我不知道爲什麼我的代碼是錯誤的。

def directedDFS(digraph, start, end, maxTotalDist): 
    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 
    for node in digraph.childrenOf(start): 
     if (str(node) not in visited): 
      visited = visited + [str(node)] 
      firststep_distance = digraph.childrenOf(start)[node][0] 
      firststep_outer_distance = digraph.childrenOf(start)[node][1] 
      if (firststep_distance <= maxTotalDist): 
       newPath = directedDFS(digraph, node, end, maxTotalDist-firststep_distance) 
       if newPath == None: 
        continue 
       if (shortest == None or TotalDistance(digraph,newPath) < TotalDistance(digraph,shortest)): 
        shortest = newPath 
    if shortest != None: 
     path = path + shortest 
    else: 
     path = None 
    return path

另一件事是，我不希望比較基於從給定節點開始的路徑的距離，而是基於整個路徑從原來的起點的距離。我不知道在這裏做這件事的最好方法。

來源

2011-05-06 Glassjawed

你的意思是跳數或距離最短（後者是微不足道的，所以我猜這是前者）？ – NPE 2011-05-06 16:12:07

您是否試圖找到包含總路徑成本（其邊緣權重之和）小於1000的最少邊的路徑？ – 2011-05-07 03:15:06

我真的不能讓你提供的代碼正面或反面（firststep_distance？firststep_outer_distance？）。你能提供你試圖實現的算法的名字嗎？

如果你只是在做一些事情，而你沒有爲了教育目的重新創建圖論，我會建議查找一個標準的最短路徑算法。如果你能保證你的權重是非負的，那麼這個標準就是Dijkstra的算法。如果您使用斐波那契堆進行備份，維基百科會報告一個改進的漸近運行時間，但不會陷入該陷阱 - 顯然，斐波那契堆在實踐中表現糟糕。

如果Dijkstra's不夠好，請查看A*-search方法。在這裏，和所有的算法問題一樣，CLR是你最好的指導，但維基百科是非常接近的。希望有所幫助！

來源

2011-05-06 16:04:35 Wang

我也真的不能告訴發生了什麼事情沒有更多的代碼或信息，但這是關於：

 if (firststep_distance <= maxTotalDist): 
      newPath = directedDFS(digraph, node, end, maxTotalDist-firststep_distance)

如果您在每次遞歸調用降低maxTotalDistance，然後firststep_distance（我假設是路徑的重量）必須大於剩餘距離，不能小於。

來源

2011-05-06 16:08:49 dfb

不，firststep_distance是路徑中第一步的權重。我應該澄清一點。 – Glassjawed 2011-05-06 16:27:11

我錯過了，按照路徑的重量，我的意思是從開始到結點的邊的權重。 – dfb 2011-05-06 16:34:20

如何在圖上找到滿足約束條件的最短路徑

回答

相關問題