#python #networkx #polygon #graph-theory
Вопрос:
Я ищу способ не только передать orgi и dest в функцию кратчайшего прохода networkx, но и некоторые дополнительные ребра/узлы, через которые должен проходить проход.
Моя цель состоит в том, чтобы использовать osmnx для создания маршрута, который будет учитывать дополнительные остановки.
до сих пор я использую функцию кратчайшего пути для передачи начала и пункта назначения. Однако я также хотел бы добавить список ребер, которые следует использовать при переходе от начала к месту назначения.
shortest_path(G, orig_edge, dest_edge, 'length')
У вас, ребята, есть какие-нибудь идеи, как легко это сделать?
Комментарии:
1. Вы должны вызвать shortest_path несколько раз, чтобы src связался с первой маршрутной точкой, с первой маршрутной точкой и со второй … последняя точка пути к месту назначения
2. хм… да, конечно, это был бы вариант, однако мне было интересно, может ли быть более эффективный способ, который я просто упустил. Тем не менее, тем временем мы сделаем это таким образом. Спасибо за ваш вклад 🙂
3. Если вызов метода не является абсурдно дорогим в python, то более эффективного способа сделать это не будет. Если вы так сильно озабочены эффективностью, вам следует использовать скомпилированный язык. C , например, примерно в 50 раз быстрее, чем python.
4. Загвоздка в том, что вам нужно упорядочить маршрутные точки так, чтобы общая длина пути была минимизирована ( я предполагаю ). Вам нужна эвристика, чтобы угадать правильный порядок путевых точек. Если вершины расположены в евклидовом пространстве, то порядок прост. В противном случае я предлагаю найти длину кратчайшего пути от источника до каждой маршрутной точки и упорядочить их, увеличив расстояние. Если количество путевых точек невелико, вы можете найти абсолютный оптимум, перепробовав все возможные порядки.