How can one find all paths between vertices in a networkx graph?

Question

Python

I have a graph and I want to find the number of paths between two specific vertices. I did not find built-in ways to find all paths in networkx, I found only finding the longest and shortest paths.

Answer 1

If not, it's easy to write your own. Recursion and elementary graph theory.
But keep in mind that this task has exponential complexity. Therefore, even if you write, it is not a fact that with a more or less serious graph you will solve your problem in a reasonable time. (Well, unless your graph is five to ten vertices). And if the graph is also not oriented, then there are, by definition, an infinite number of solutions.
Therefore, for practical needs, restrictions are usually formulated that make it possible to reduce the range of options considered and solve real practical problems.
Here is an elementary explanation:
kuimova.ucoz.ru/modul_10-grafy-bazovye_algoritmy.pdf
Here is a draft script
https://ru.stackoverflow.com/questions/1046271/alg...
Here - if you start writing - some useful
discussions
and
ideas delphikingdom.com/asp/answer.asp?IDAnswer=56734

Answer 2

I'm assuming you only want simple paths, no self-intersections on vertices. Otherwise, there can be infinitely many paths.
There is no ready-made solution, because it is a rather rare task to get all the paths. By the way, even without self-intersections, there can be exponentially many paths. Already for 15 vertices there is a trivial graph in which there are almost 100 billion simple paths between any two vertices.
If you need to iterate over paths to choose the best one, or to assemble a combination (say, k non-intersecting parallel paths, or several shortest paths), then there are almost certainly faster algorithms than iterating over all paths. Write your task - they will prompt you.
But if you really need all the paths, then the only way is to brute-force through depth-first traversal. In a standard traversal, you only mark vertices as you enter them. In the same problem, you will have to unmark a vertex before exiting it. The problem with this method is that it is quite slow.
Something like this. I'm not a pythonist, so maybe with errors, but the idea should be clear.

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())