@alligator3000

Как можно найти все пути между вершинами графа networkx?

У меня есть граф и я хочу найти количество путей между двумя определенными вершинами. Встроенных способов нахождения всех путей в networkx я не нашёл, нашёл только нахождение самого длинного и короткого пути.
  • Вопрос задан
  • 60 просмотров
Пригласить эксперта
Ответы на вопрос 2
@dmshar
Если нет - легко написать самому. Рекурсия и элементарная теория графов.
Но надо иметь ввиду, что эта задача имеет экспоненциальную сложность. Поэтому даже если напишете - не факт, что при более-менее серьезном графе решите вашу задачу за вразумительное время. (Ну, если ваш граф не на пять-десять вершин). А если граф еще и не ориентированный - то решений вообще по определению бесконечное число.
Поэтому для практических нужд обычно формулируют ограничения, которые позволяют сократить круг рассматриваемых вариантов и решать реальные практические задачи.
Вот тут - элементарное объяснение:
kuimova.ucoz.ru/modul_10-grafy-bazovye_algoritmy.pdf
Вот тут - некий драфт скрипта
https://ru.stackoverflow.com/questions/1046271/алг...
Вот тут - если начнете писать - некоторые полезные обсуждения и идеи
https://coderoad.ru/2723438/Алгоритм-Графа-Для-Пои...
www.fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rul...
www.delphikingdom.com/asp/answer.asp?IDAnswer=56734
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Я предполагаю, что вам нужны только простые пути, без самопересечений по вершинам. Иначе путей может быть бесконечно много.

Готового решения нет, потому что это довольно редкая задача - получить все пути. Кстати, даже без самопересечений путей может быть экспоненциально много. Уже для для 15 вершин есть тривиальный граф, в котором почти 100 миллиардов простых путей между любыми двумя вeршинами.

Если вам надо перебрать пути, чтобы выбрать из них лучший, или собрать комбинацию (допустим, k не пересекающихся параллельных путей или несколько кратчайших путей), то почти наверняка есть более быстрые алгоритмы, чем перебор всех путей. Напишите вашу задачу - вам подскажут.

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

Что-то типа такого. Я не питонист, так что возможно с ошибками, но идея должна быть понятна.

def dfs(v, end, graph, path, visited):
  if v == end:
    print(path)
    return
  for u in graph.neighbours(v):
    if u not in visited:
      path.append(u);
      visited.add(u);
      dfs(u, end, graph, path, visited)
      path.pop();
      visited.remove(u);

// вызывать dfs(start, end, graph, [], set())
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Softaria Новосибирск
от 100 000 до 150 000 ₽
от 150 000 ₽
LEX BOREALIS Волгоград
от 90 000 ₽
12 апр. 2021, в 02:45
500 руб./за проект
12 апр. 2021, в 02:02
800 руб./за проект
11 апр. 2021, в 22:49
1000 руб./за проект