Путь между двумя узлами

Question

Я использую networkx для работы с графиками. У меня довольно большой график (в нем около 200 узлов), и я пытаюсь найти все возможные пути между двумя узлами. Но, как я понимаю, networkx может найти только кратчайший путь. Как я могу получить не только кратчайший путь, но и все возможные пути?

UPD: путь может содержать каждый узел только один раз.

UPD2: мне нужно что-то вроде функции find_all_paths(), описанной здесь: python.org/doc/essays/graphs.html Но эта функция плохо работает с большим количеством узлов и имеет edged =(

Answer 1

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], circular=False) в игре). Количество кратчайших путей, ведущих от верхнего левого узла к нижнему правому узлу, равно числу возможностей выбора 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.

Answer 2

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

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths

Answer 3

Алгоритм Дейкстры найдет кратчайший путь способом, подобным поиску в ширину (он заменяет приоритетную очередь, взвешенную по глубине, в граф для наивной очереди BFS). Вы можете довольно просто расширить его, чтобы получить N кратчайших путей, если вам нужно некоторое количество альтернатив, хотя если вам нужно, чтобы пути существенно отличались (например, планирование маршрутов фургонов безопасности), возможно, вам нужно быть более умным в выборе пути, которые значительно отличаются друг от друга.