python - 如何返回第一个有效路径？

Question

这个问题已经有答案了:

Find path from a list of tuples in Python (3 个回答)

已关闭 7 年前。

我有一个模拟图表的大型数据集，其中包含城市及其之间的距离。它存储为元组列表:

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, Baltimore, New York City, Orlando, San Francisco, 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

构造一个加权graph为您的对象建模并使用graph traversal algorithms找到你的道路。

特别是，Dijkstra's algorithm您可能感兴趣。它找到起始节点和最终节点之间可能的最短路径。第一段甚至给出了道路网络作为其应用的例子。

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

根据评论，如果您不关心找到最短的可能路径，则递归 depth-first search也将以较小的时间复杂度解决您的问题。