Мне интересно, каков наиболее эффективный способ проверки того, что все целевые узлы из набора T достижимы хотя бы из одного исходного узла S в библиотеке Python NetworkX.
Для меня это должно бытьпростой вызов функции Dijkstra «многие ко многим», где S - вход списка исходных узлов, а T - вход списка целевых узлов.Затем я мог убедиться, что возвращаемое значение указывает, что по крайней мере одна из маршрутов была успешной.Вот как я мог бы подойти к проблеме, используя расширение pgRouting PostgreSQL, для тех, кто может быть знаком с этим:
pgr_dijkstra(edges_sql, start_vids, end_vids)
Однако, кажется из документации, что функция, где и источники, и целисписки не существует .Самое близкое, что я мог найти, это multi_source_dijkstra или all_pairs_dijkstra.
. Мне кажется, что multi_source_dijkstra недостаточно, потому что я не могу указать список из нескольких целевых узлов в качестве входных данных, и что all_pairs_dijkstra слишком много, потому чтоЯ не хочу тратить время на тестирование соединения между исходными узлами или между целевыми узлами.Кроме того, я полностью ожидаю, что мой граф будет иметь пробелы внутри себя, и я просто хочу проверить исходное условие - все целевые узлы просто доступны по крайней мере из одного исходного узла.
Я уверен, что что-томожно объединить функцию multi_source_dijkstra, но я хочу, чтобы это было как можно более эффективным, поэтому я надеюсь, что мне просто не хватает очевидной реализации, которая бы делала то, что я хочу, наиболее эффективно.
РЕДАКТИРОВАТЬ: Изображениедля @abc.Красные / желтые, красные / розовые линии и зеленые линии представляют подграф, который я использую в алгоритме DFS или BFS.Эта конфигурация возвращает True, утверждая, что все красные точки (цели) достижимы от зеленой точки (источника).
