Python Dijkstra k кратчайшие пути

Я пытаюсь сделать небольшое приложение для маршрутизации общественного транспорта.

Мои данные представлены в следующей структуре:

graph = {'A': {'B':3, 'C':5}, 'B': {'C':2, 'D':2}, 'C': {'D':1}, 'D': {'C':3}, 'E': {'F':8}, 'F': {'C':2}} 

Где:

  1. graph dict key – это узел
  2. subdict – это край между двумя узлами
  3. значение subdict – это вес края

Я использовал алгоритм find_shortest_path, описанный здесь https://www.python.org/doc/essays/graphs/, но он довольно медленный из-за рекурсии и не имеет поддержки весов.

Поэтому я перешел к алгоритму, описанному Давидом Эпштейном, здесь http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ (и даже лучшая реализация может быть найдена там в комментариях с использованием heapq)

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

Может ли кто-нибудь помочь мне в этом, пожалуйста, или, по крайней мере, дать направление? Я не очень хорош в алгоритмах кратчайших путей графика.

Заранее спасибо!

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

Алгоритм

  1. Запустите алгоритм Дейкстры из начальной точки и получите список disS [i] (кратчайшее расстояние между начальной точкой и точкой i). А затем запустить алгоритм Дейкстры из конечной точки и получить список disT [i] (кратчайшее расстояние между конечной точкой и точкой i)
  2. Создайте новый график: для края в исходном графе, если disS [a] + disT [b] + w (a, b) == disS [конечная точка], мы добавим ребро в новый граф. Очевидно, что новый график представляет собой DAG (Directized acyclic graph) и имеет приемник (начальную точку) и цель (конечную точку). Любой путь от приемника до цели будет самым коротким путем в исходном графе.
  3. Вы можете запустить DFS на новом графике. Сохраняйте информацию о пути в рекурсии и обратном отслеживании, в любой момент, когда вы достигнете цели, сохраненная информация будет одним кратчайшим путем. Когда окончание алгоритма зависит от вас.

Псевдокод:

 def find_one_shortest_path(graph, now, target, path_info): if now == target: print path_info return for each neighbor_point of graph[now]: path_info.append(neighbor_point) find_one_shortest_path(graph, neighbor_point, target, path_info) #recursion path_info.pop(-1) #backtracking def all_shortest_paths(graph, starting_point, ending_point): disS = [] # shortest path from S disT = [] # shortest path from T new_graph = [] disS = Dijkstra(graph, starting_point) disT = Dijkstra(graph, endinng_point) for each edge<a, b> in graph: if disS[a] + w<a, b> + disT[b] == disS[ending_point]: new_graph.add(<a, b>) find_one_shortest_path(new_graph, starting_point, ending_point, []) 

У Networkx есть функция, чтобы сделать это all_shortest_paths .

Он возвращает генератор всех кратчайших путей.

Я столкнулся с аналогичной проблемой в анализе транспортной сети. Я использовал отличный модуль python NetworkX. Он имеет функцию генерации всех простых путей между двумя узлами. Ссылка здесь:

http://networkx.lanl.gov/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html