Путь между двумя узлами
Я использую networkx для работы с графиками. У меня есть довольно большой график (это близко 200 узлов в нем), и я пытаюсь найти все возможные пути между двумя узлами. Но, поскольку я понимаю, networkx может найти только кратчайший путь. Как я могу получить не только кратчайший путь, но и все возможные пути?
UPD: путь может содержать каждый узел только однажды.
UPD2: Мне нужно что-то как find_all_paths () функция, описанная здесь: python.org/doc/essays/graphs.html, Но эта функция не работает хорошо с большим количеством узлов и ограниченный = (
2 ответа
igraph , другой модуль графа для Python может вычислять все кратчайшие пути между заданной парой узлов. Вычислять все пути не имеет смысла, так как таких путей бесконечно много.
Пример вычисления всех кратчайших путей из вершины 0:
>>> from igraph import Graph
>>> g = Graph.Lattice([10, 10], circular=False)
>>> g.get_all_shortest_paths(0)
[...a list of 3669 shortest paths starting from vertex 0...]
Если у вас igraph 0.6 или новее (это разрабатываемая версия на момент написания), вы можете ограничить результат get_all_shortest_paths к заданной конечной вершине:
>>> g.get_all_shortest_paths(0, 15)
[[0, 1, 2, 3, 4, 14, 15],
[0, 1, 2, 12, 13, 14, 15],
[0, 10, 11, 12, 13, 14, 15],
[0, 1, 11, 12, 13, 14, 15],
[0, 1, 2, 3, 13, 14, 15],
[0, 1, 2, 3, 4, 5, 15]]
Конечно, вы должны быть осторожны; например, предположим, что у вас есть сеточный график 100 x 100 (который можно легко сгенерировать с помощью Graph.Lattice ([100, 100], круговой = False) в igraph).Количество кратчайших путей, ведущих от верхнего левого узла к нижнему правому узлу, равно количеству возможностей выбрать 100 элементов из 200 (доказательство: длина кратчайшего пути имеет 200 ребер, 100 из которых будут идти «по горизонтали». в сетке и 100 из которых пойдут «по вертикали»). Это, вероятно, не умещается в вашей памяти, поэтому даже вычисление всех кратчайших путей между этими двумя узлами здесь нереально.
Если вам действительно нужны все пути между двумя узлами, вы можете переписать функцию, указанную на упомянутой вами веб-странице, используя igraph, что, вероятно, будет быстрее, чем решение на чистом Python, поскольку ядро igraph реализовано на C:
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
paths = []
for node in set(graph.neighbors(start)) - set(path):
paths.extend(find_all_paths(graph, node, end, path))
return paths
Это можно еще больше оптимизировать, сначала преобразовав граф в представление списка смежности, поскольку это избавит от повторных вызовов graph.neighbors :
def find_all_paths(graph, start, end):
def find_all_paths_aux(adjlist, start, end, path):
path = path + [start]
if start == end:
return [path]
paths = []
for node in adjlist[start] - set(path):
paths.extend(find_all_paths_aux(adjlist, node, end, path))
return paths
adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())]
return find_all_paths_aux(adjlist, start, end, [])
Изменить : исправлен первый пример для работы в igraph 0.5.3 как ну не только в igraph 0.6.
Алгоритм Дейкстры находит кратчайший путь способом, похожим на поиск по ширине (он заменяет приоритетную очередь, взвешенную по глубине графа, на наивную очередь BFS). Вы можете довольно тривиально расширить его для получения 'N' кратчайших путей, если вам нужно некоторое количество альтернатив, хотя если вам нужно, чтобы пути существенно отличались друг от друга (например, планирование маршрутов охранных фургонов), вам, возможно, придется быть более умным в выборе путей, которые существенно отличаются друг от друга.