Как вернуть первый допустимый путь?

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, 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

Чтобы вернуть путь между двумя узлами в графе, если он не обязательно должен быть самым коротким, можно использовать 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 может заинтересовать вас. Он находит кратчайший путь между стартовым узлом и конечным узлом. Первый абзац даже дает дорожные сети в качестве примера его применения.

Алгоритм Дейкстры является алгоритмом поиска кратчайших путей между узлами в графе, которые могут представлять собой, например, дорожные сети.

Согласно комментариям, если вы не заботитесь о поиске кратчайшего пути, рекурсивный depth-first search будет также решить вашу проблему с меньшим временем сложности.