Я предполагаю, что вам нужны только простые пути, без самопересечений по вершинам. Иначе путей может быть бесконечно много.
Готового решения нет, потому что это довольно редкая задача - получить все пути. Кстати, даже без самопересечений путей может быть экспоненциально много. Уже для для 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())
