Как перебрать для всех вершин все пути до других вершин
У меня есть ориентированный граф
Мне нужно сделать вот такой перебор:
Берём вершину 2. Перебираем все пути от вершины 2 до вершины 3 (один путь: 2->3). Далее перебираем все вершины от 2 до 4 (два пути: 2->3->4, 2->4). Далее от 2 до 5 и до самой последней (здесь до 5)
В общем, для каждой вершины перебрать все пути до других вершин.
Два вопроса:
Как сделать этот перебор в графе представленном матрицей смежности, можно код на Python
Возможно ли это оптимизировать, потому что перебирать столько путей будет очень медленно
Ответы (1 шт):
Используйте доработанный поиск в ширину (или в глубину)
В отличие от обычного BFS пометки о посещении пройденных вершин должны быть не глобальными, а локальными для каждой ветви рекурсии.
Это можно осуществить, передавая новый экземпляр пометок (visited) в рекурсивный вызов, либо работать с одним экземпляром, но очищать пометку обрабатываемой вершины после рекурсивного вызова.