如何返回第一個有效路徑？

Question

我有一個模擬圖的大型數據集，其中包含城市以及它們之間的距離。它被存儲爲元組的列表：

map = [('Baltimore', 'New York City', 85), 
('Dallas', 'Cincinatti', 104), 
('Denver', 'Salt Lake City', 91), 
('Orlando', 'New York City', 17), 
('Orlando', 'San Francisco', 64), 
('Seattle', 'Baltimore', 89), 
('Seattle', 'Portland', 44), 
('Portland', 'Las Vegas', 32), 
('Las Vegas', 'Reno', 7), 
('Reno', 'Chicago', 29), 
('Chicago', 'San Francisco', 56)] 

這表明頂點兩者之間的「巴爾的摩」和「紐約城」有我試圖用深度優先搜索和寫入的方法85的距離可以採取一個起點城市和一個最終城市，並返回一條有效路徑（如果存在或存在多條路徑），將連接兩條路徑和總距離。例如，如果start_city ='Baltimore'和end_city ='San Francisco'，它將打印：YES，巴爾的摩，紐約市，奧蘭多，舊金山，166。我需要的是我的代碼返回是一條有效的路徑總距離。

def dfs_helper(map, start_city, end_city): 
    stack = [] 
    visited = [] 
    adj_cities = get_connections(map, start_city) 
    dfs_visit(map, start_city, end_city, adj_cities, stack, visited) 

def dfs_visit(results, start_city, end_city, adj_cities, stack, visited): 
    #mark start_city as visited 
    visited.append(start_city) 

    if(end_city in visited): #soon as end_city is discovered, return the path it took to get there. 
     return stack 

    for adj_city in adj_cities: 
     #add adj_city to stack to keep track of that path to the end_city 
     stack.append(adj_city) 
     if adj_city not in visited: 
      adj_cities = get_connections(results, adj_city) 
      dfs_visit(map, adj_city, end_city, adj_cities, stack, visited) 

def get_connections(map, city): 
    connections = [] 

    for result in map: 
     if (result[0] == city): 
      connections.insert(0, result[1]) 
     elif (result[1] == city and result[0] != city): 
      connections.insert(0, result[0]) 

    connections.reverse() 
    return connections 

我這樣稱呼它：dfs_helper(map, "Baltimore", "San Francisco")

Answer 1

要返回圖中兩個節點之間的路徑，如果它不一定需要最短，可以使用Recursive DFS。它需要參數start_city和end_city，將總成本從start_city返回到end_city。但是，如果您還需要打印路徑，則可以打印前趨向量。這是一個想法：

def dfs_visit(start_city): 
    mark start_city as visited 

    if(end_city is discovered) //soon as end_city is discovered, return the path it took to get there. 
     return stack 

    for each adj_city of start_city: 
     add adj_city to stack //to keep track of that path to the end_city 
     if adj_city is not discovered: 
      dfs_visit(adj_city) 

重複此過程，直到沒有頂點未被發現。

Answer 2

構建一個加權graph建模你的對象，並使用graph traversal algorithms找到自己的路徑。

特別是，您可能感興趣的是Dijkstra's algorithm。它找到起始節點和最終節點之間可能的最短路徑。第一段甚至將道路網絡作爲其應用的一個例子。

Dijkstra算法是一種算法，用於查找圖中節點之間的最短路徑，例如可能表示道路網絡。

根據評論，如果你不關心尋找最短的路徑，遞歸的depth-first search也將解決你的問題，以較小的時間複雜性。