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

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

Алгоритм

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