Find all the paths between two nodes of the graph

Question

I am working on a Dijkstra algorithm to get the shortest path between interconnected nodes in a route network. I have a job. It returns all the shortest paths to all nodes when I pass the start node to the algorithm.

My question is: How can I get all possible paths from node A to say node G or even all possible paths from node A and back to node A

Answer 1

Finding all possible paths is a difficult problem, since there is an exponential number of simple paths. Even the search for the k-th shortest path [or the longest path] is NP-Hard .

One of the possible solutions to search all paths [or all paths to a certain length] from s to t is BFS , without saving the visited set or for the weighted version - you can use a uniform cost search

Note that also in every graph that has cycles [this is not a DAG ], there can be an infinite number of paths between s and t .

Answer 2

I will give you a (somewhat small) version (albeit understandable, I think) of scientific evidence that you cannot do this for an acceptable amount of time.

What I will prove is that the time complexity of listing all the simple paths between two selected and different nodes (for example, s and t ) in an arbitrary graph G not polynomial. Please note that since we only care about the number of paths between these nodes, the cost of cross is unimportant.

I am sure that if a graph has some well-selected properties, it can be easy. However, I am considering a general case.

---

Suppose we have a polynomial algorithm that lists all the simple paths between s and t .

If G connected, the list is not empty. If G not, and s and t are in different components, it is very easy to list all the paths between them, because they are not! If they are in one component, we can pretend that the entire graph consists only of this component. Therefore, suppose that G indeed connected.

The number of listed paths must be polynomial, otherwise the algorithm could not return everything to me. If he lists all of them, he should give me the longest, so he is there. With a list of paths, you can use a simple procedure to tell me this longest path.

We can show (although I cannot think of a connected way of saying this) that this longest path must cross all the vertices of G So we just found a Hamiltonian path with a polynomial procedure! But this is a well-known NP-hard problem.

Then we can conclude that this polynomial algorithm, which we thought we had, hardly exists if P = NP .

Answer 3

I implemented a version where it basically finds all possible paths from one node to another, but it does not take into account any possible “cycles” (the graph that I use is cyclical). Thus, no node will appear twice in the same path. And if the graph was acyclic, then I suppose you could say that it finds all possible paths between these two nodes. It seems to work fine, and for my graph size of ~ 150 it works almost instantly on my machine, although I am sure that the runtime should be something like exponential, and therefore it will start to slow down quickly as the graph gets bigger.

Here is some Java code that demonstrates what I implemented. I am sure there must be more efficient or elegant ways to do this.

 Stack connectionPath = new Stack(); List<Stack> connectionPaths = new ArrayList<>(); // Push to connectionsPath the object that would be passed as the parameter 'node' into the method below void findAllPaths(Object node, Object targetNode) { for (Object nextNode : nextNodes(node)) { if (nextNode.equals(targetNode)) { Stack temp = new Stack(); for (Object node1 : connectionPath) temp.add(node1); connectionPaths.add(temp); } else if (!connectionPath.contains(nextNode)) { connectionPath.push(nextNode); findAllPaths(nextNode, targetNode); connectionPath.pop(); } } } 

Answer 4

Here is an algorithm that finds and prints all paths from s to t using a DFS modification. In addition, dynamic programming can be used to count the number of possible paths. The pseudocode will look like this:

 AllPaths(G(V,E),s,t) C[1...n] //array of integers for storing path count from 's' to i TopologicallySort(G(V,E)) //here suppose 's' is at i0 and 't' is at i1 index for i<-0 to n if i<i0 C[i]<-0 //there is no path from vertex ordered on the left from 's' after the topological sort if i==i0 C[i]<-1 for j<-0 to Adj(i) C[i]<- C[i]+C[j] return C[i1] 

Answer 5

Usually you do not want this because there is an exponential number of them in nontrivial graphs; if you really want to get all (simple) paths or all (simple) loops, you just find one (skipping the graph) and then go back to the other.

Answer 6

I think what you want is some form of Ford-Fulkerson algorithm based on BFS. It is used to calculate the maximum network flow by finding all the expansion paths between two nodes.

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

Answer 7

I assume that you want to find “simple” paths (the path is simple if node does not appear in it, with the possible exception of the first and last).

Since the problem is NP-hard, you might want to do a depth search option.

Basically, generate all possible paths from A and check if they fall into G.

Answer 8

There is a good article that can answer your question (only it prints the paths, but does not collect them). Note that you can experiment with C ++ / Python samples in an online environment.

http://www.geeksforgeeks.org/find-paths-given-source-destination/

Answer 9

find_paths [s, t, d, k]

This question is a little old now ... but I will throw my hat in the ring.

I personally found the form algorithm find_paths[s, t, d, k] useful, where:

• s is the starting node
• t - target node
• d - maximum depth to search
• k - the number of paths to search

Using your form of the infinity programming language for d and k will give you all the ways.

§ Obviously, if you use a directed graph and want all the non-oriented paths between s and t , you will have to run these two methods:

 find_paths[s, t, d, k] <join> find_paths[t, s, d, k] 

---

Helper function

I personally like recursion, although it can be complicated several times, in any case, it allows us to define our helper function first:

 def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found) current_path.append(current) if current_depth > max_depth: return if current == goal: if len(paths_found) <= number_of_paths_to_find: paths_found.append(copy(current_path)) current_path.pop() return else: for successor in graph[current]: self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found) current_path.pop() 

Main function

From this point of view, the main function is trivial:

 def find_paths[s, t, d, k]: paths_found = [] # PASSING THIS BY REFERENCE find_paths_recursion(s, t, 0, d, k, [], paths_found) 

---

First, pay attention to a few things:

• the above pseudocode is a markup of languages, but most closely resembles python (since I just encoded in it). Strict copy-paste will not work.
• [] - uninitialized list, replace it with the equivalent for your chosen programming language.
• paths_found is passed by reference . It is clear that the recursion function does not return anything. Handle it accordingly.
• here graph takes some kind of hashed structure. There are many ways to implement a schedule. In any case, the graph[vertex] gets a list of adjacent vertices in the oriented graph - adjust accordingly.
• it is assumed that you have pre-processed to remove self-loops, loops and polyhedra