There are built-in methods to find a shortest path between two vertices in a graph, and the question on finding all shortest paths between two vertices has gathered quite a bit of attention.
A path is simple if it repeats no vertices. As is with all shortest paths between a pair of vertices, the number of simple paths between two vertices can be huge. What would be a nice and clean method of finding all simple paths between two vertices?
Assume the input graph is undirected, simple, and it may have cycles in it. I am not interested in the number of simple paths between $s$ and $t$, but I want to explicitly enumerate all of them. Furthermore, note that this problem cannot be solved in polynomial time. Even writing the output might take time that is not polynomial in the number of vertices.
One way of listing the simple paths is to use depth-first search. Maybe DepthFirstScan is useful here. The DFS can avoid repeating vertices by marking them as they are visited in the recursion, and then removing the mark just before returning from the recursive call. I learned a backtracking solution might not be that fast.
Answer
You can use the new FindPath function that comes with Mathematica 10. A simple example:
g = CompleteGraph[4];
FindPath[g, 1, 2, Infinity, All]
(* Output: {{1,2},{1,4,2},{1,3,2},{1,4,3,2},{1,3,4,2}} *)
The function also accepts parameters, so you can find a path (or all paths) of specific length. See the docs for more.
Comments
Post a Comment