Найти все пути между источником назначения с ограничением длины пути

Question

Я использую python 2.7 и networkx.

У меня довольно большая сеть, и мне нужно найти все пути (не только кратчайший путь) между источником и пунктом назначения. Поскольку моя сеть большая, я хотел бы ускорить некоторые ограничения, такие как длина пути, стоимость и т. Д.

Я использую networkx. Я не хочу использовать all_simple_paths, потому что с all_simple_paths, я должен фильтровать все пути позже на основе длины пути (количество узлов в нем) или стоимость пути (на основе затрат на дуги). Фильтрация всех путей очень дорога для большой сети.

Я бы очень признателен за любую помощь.

Answer 1

Это действительно зависит от того, какие пути вы ищете.

Во-первых, кратчайший путь дает вам нижнюю границу c_min по ограничению длины. Затем, учитывая ограничение длины c>=c_min, для каждого узла n вы знаете кратчайший путь P_s_n и расстояние c_n от начала до этого узла. Выберите те узлы, которые удовлетворяют c_n <c. Затем вы можете произвольно растянуть P_s_n по любому пути от n до цели, которая удовлетворит ограничение длины.