Python Самый короткий путь между двумя точками

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

[(A,B),(C,D),(B,C),(D,E)...] # list of possible paths

Если мы предполагаем, что мне нужен путь от A до E, результат должен быть:

(A,B)=>(B,C)=>(C,D)=>(D,E)

но я не могу найти pythonic способ сделать этот поиск.

3 ответа

Путь Pythonic состоит в том, чтобы использовать модуль, если он существует. Как и в этом случае, мы знаем, что networkx есть, мы можем написать

Реализация

import networkx as nx
G = nx.Graph([('A','B'),('C','D'),('B','C'),('D','E')])
path = nx.shortest_path(G, 'A', 'E')

Вывод

zip(path, path[1:])
[('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E')]


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

Созданный таким образом, ваша проблема - это просто классическая проблема с коротким пути.

Вы попросили питоновский способ написать это. Единственный совет, который я бы дал, представляет ваш график как словарь, так что каждый ключ является точкой, возвращаемые значения представляют собой список других точек, которые можно достичь непосредственно с этой точки. Это ускорит перемещение графика. graph[C] → [B, D] для вашего примера.


Вот решение, использующее A *:

pip install pyformulas==0.2.8

import pyformulas as pf

transitions = [('A', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'F'), ('D', 'F'), ('F', 'D'), ('F', 'B'), ('D', 'E'), ('E', 'C')]

initial_state = ('A',)

def expansion_fn(state):
 valid_transitions = [tn for tn in transitions if tn[0] == state[-1]]
 step_costs = [1 for t in valid_transitions]

 return valid_transitions, step_costs

def goal_fn(state):
 return state[-1] == 'E'

path = pf.discrete_search(initial_state, expansion_fn, goal_fn) # A*
print(path)

Вывод:

[('A',), ('A', 'B'), ('B', 'C'), ('C', 'F'), ('F', 'D'), ('D', 'E')]

licensed under cc by-sa 3.0 with attribution.