找到從頭到尾頂點的圖中的最短路徑

-1

我正試圖在圖中找到所有可能路徑中的最短路徑。我寫了下面的程序，當我嘗試從頂點'A'到'D'搜索路徑時，它返回['A'，'B'，'C'，'D']。但最短的距離是['A'，'B'，'D']。有沒有辦法找到它，因爲我已經找到了所有可能的節點？找到從頭到尾頂點的圖中的最短路徑

from collections import defaultdict 


def find_path(graph,start,end,path=[]): 
    path = path + [start] 
    print "intermediate", path 
    if start == end: 
     return path 
    if not graph.has_key(start): 
     return None 
    for node in graph[start]: 
     print "node",node 
     if node[1] not in path: 
      newpath = find_path(graph,node[1],end,path) 
      if newpath : 
       return newpath 
    return None 

if __name__ == '__main__': 
    graph = defaultdict(list) 
    graph = { 
      'A': [('A','B'),('A','C')], 
      'B' : [('B','C'),('B','D')], 
      'C' : [('C','D')], 
      'D' : [('D','C')], 
      'E' : [('E','F')], 
      'F' : [('F','C')] 
      } 

    path = find_path(graph,'A','D')

來源

2015-11-06 Tammy

您的代碼無處檢查路徑的長度，或者保留迄今爲止最短路徑的記錄，或者在找到一條路徑後繼續嘗試查找路徑。你需要做大部分。 –

閱讀關於鄰接表和Djikstra的圖的最短路徑算法。 – goelakash

Dijkstra的algorthim是您可能想要查看的一個選項。一些示例代碼可以在這裏找到：http://www.bogotobogo.com/python/python_Dijkstras_Shortest_Path_Algorithm.php –

我現在增加了一個新函數，它通常是一個貪婪算法。如果它看到一個連接到「結束」節點的節點，它會關閉遞歸。感謝@Jonathan的建議。將欣賞任何批評這種方法。

def shortest_path(graph,start,end,short_path=[]): 
    short_path = short_path + [start] 
    #print "Initial short path",short_path 
    if start == end: 
     return short_path 
    if not graph.has_key(start): 
     return None 
    for node in graph[start]: 
     #print "short node",graph[start] 
     vend = [x[1] for x in graph[start] if x[1] == end] 
     print "v_end",vend 
     if vend : 
      if vend[0] == end: 
       #print "printing end nodes",vend,start 
       tmp_path = shortest_path(graph,end,end,short_path) 
       if tmp_path: 
        #print "shortest intermediate path",tmp_path 
        return tmp_path 

     elif node[1] not in short_path: 
      tmp_path = shortest_path(graph,node[1],end,short_path) 
      #print tmp_path, "start",node[1], "end",end 
      if tmp_path: 
       #print "shortest intermediate",tmp_path 
       return tmp_path 
     else: 
      return None

來源

2015-11-06 18:07:03 Tammy

這不會起作用，它會跳轉到如果它在1個鏈接之內，但它仍然不關心在端節點的1個鏈接中需要多長時間的路徑。 – user2357112

找到從頭到尾頂點的圖中的最短路徑

回答

相關問題