как найти кратчайший путь между всеми городами с начальной и конечной точками

Question

У меня есть такой фрейм данных,

 From City      City A  City B City C  City D
 City A                 2166    577     175
 City B         2166            1806    2092
 City C         577     1806            653
 City D         175     2092    653 

Я нашел порядок кратчайшего пути, используя tsp-solver, но я хочу найти порядок кратчайшего пути с начальной и конечной точками . Просьба помочь

ожидаемый результат:

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

Answer 1

Я не знаю, правильно ли я понял вопрос, но если вам нужен упорядоченный список городов с кратчайшим путем из выбранного города, вы можете сделать это так:

df = pd.DataFrame({"From city": ['A', 'B', 'C', 'D'], 'A':[np.NaN,2166,577,175], 'B':[2166,np.NaN,1806,2092], 'C':[577,1806,np.NaN,653], 'D':[175,2092,653,np.NaN]})
df.set_index('From city', inplace=True)
print df
                A       B       C       D
From city                                
A             NaN  2166.0   577.0   175.0
B          2166.0     NaN  1806.0  2092.0
C           577.0  1806.0     NaN   653.0
D           175.0  2092.0   653.0     NaN

dic = df.to_dict(orient='records')
city=dic[3]
from math import isnan
city = {k: city[k] for k in city if not isnan(city[k])}
city_order = sorted(city.items(), key=lambda x:x[1])
city_list = [i[0] for i in city_order]

Пояснение:

Сделать словарь из df:

dic = df.to_dict(orient='records')

Выберите свой город (для города 'D' -> 3)

city=dic[3]

Удалить элемент NaN

from math import isnan
city = {k: city[k] for k in city if not isnan(city[k])}

Заказать

city_order = sorted(city.items(), key=lambda x:x[1])

Взять только города:

city_list = [i[0] for i in city_order]
print city_list

Выход:

['A', 'C', 'B']