Find all paths between two graph nodes

Question

I am working on an implementation of Dijkstra's Algorithm to retrieve the shortest path between interconnected nodes on a network of routes. I have the implementation working. It returns all the shortest paths to all the nodes when I pass the start node into the algorithm.

My question: How does one go about retrieving all possible paths from Node A to, say, Node G or even all possible paths from Node A and back to Node A?

Solution 1

Finding all possible paths is a hard problem, since there are exponential number of simple paths. Even finding the kth shortest path [or longest path] are NP-Hard.

One possible solution to find all paths [or all paths up to a certain length] from s to t is BFS, without keeping a visited set, or for the weighted version - you might want to use uniform cost search

Note that also in every graph which has cycles [it is not a DAG] there might be infinite number of paths between s to t.

Solution 2

I've implemented a version where it basically finds all possible paths from one node to the other, but it doesn't count any possible 'cycles' (the graph I'm using is cyclical). So basically, no one node will appear twice within the same path. And if the graph were acyclical, then I suppose you could say it seems to find all the possible paths between the two nodes. It seems to be working just fine, and for my graph size of ~150, it runs almost instantly on my machine, though I'm sure the running time must be something like exponential and so it'll start to get slow quickly as the graph gets bigger.

Here is some Java code that demonstrates what I'd implemented. I'm sure there must be more efficient or elegant ways to do it as well.

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

Solution 3

I'm gonna give you a (somewhat small) version (although comprehensible, I think) of a scientific proof that you cannot do this under a feasible amount of time.

What I'm gonna prove is that the time complexity to enumerate all simple paths between two selected and distinct nodes (say, s and t) in an arbitrary graph G is not polynomial. Notice that, as we only care about the amount of paths between these nodes, the edge costs are unimportant.

Sure that, if the graph has some well selected properties, this can be easy. I'm considering the general case though.

---

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

If G is connected, the list is nonempty. If G is not and s and t are in different components, it's really easy to list all paths between them, because there are none! If they are in the same component, we can pretend that the whole graph consists only of that component. So let's assume G is indeed connected.

The number of listed paths must then be polynomial, otherwise the algorithm couldn't return me them all. If it enumerates all of them, it must give me the longest one, so it is in there. Having the list of paths, a simple procedure may be applied to point me which is this longest path.

We can show (although I can't think of a cohesive way to say it) that this longest path has to traverse all vertices of G. Thus, we have just found a Hamiltonian Path with a polynomial procedure! But this is a well known NP-hard problem.

We can then conclude that this polynomial algorithm we thought we had is very unlikely to exist, unless P = NP.

Solution 4

The following functions (modified BFS with a recursive path-finding function between two nodes) will do the job for an acyclic graph:

from collections import defaultdict

# modified BFS
def find_all_parents(G, s):
    Q = [s]
    parents = defaultdict(set)
    while len(Q) != 0:
        v = Q[0]
        Q.pop(0)
        for w in G.get(v, []):
            parents[w].add(v)
            Q.append(w)
    return parents

# recursive path-finding function (assumes that there exists a path in G from a to b)   
def find_all_paths(parents, a, b):
    return [a] if a == b else [y + b for x in list(parents[b]) for y in find_all_paths(parents, a, x)]

For example, with the following graph (DAG) G given by

G = {'A':['B','C'], 'B':['D'], 'C':['D', 'F'], 'D':['E', 'F'], 'E':['F']}

if we want to find all paths between the nodes 'A' and 'F' (using the above-defined functions as find_all_paths(find_all_parents(G, 'A'), 'A', 'F')), it will return the following paths:

Solution 5

Here is an algorithm finding and printing all paths from s to t using modification of DFS. Also dynamic programming can be used to find the count of all possible paths. The pseudo code 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]

View more solutions

Comments

[zmccord]

Well, if your graph has cycles, that could be an extremely long list.

[Liam Mencel]

Do you want paths that don't repeat vertices/edges?

[Paul]

@ HexTree I'm not too sure what you mean. Each vertice is unique. I'm basically looking for each path the weight of that path and the number of nodes that were touched via each path

[Saeed Amiri]

Why you want to find all paths? If your question is how to reroute when some nodes failed or etc, there are some algorithms (heuristics). but your current case is very general and is np-hard.

[SumNeuron]

@Paul please consider my new answer which is robust solution to your question

[Diego]

It's simple, efficient and doable for any DAG. You are misleading @Paul.

[Paul]

Thanks amit I will try looking at BFS or the uniform cost search

[amit]

@Paul: You are welcome. just make sure in both of them you don't use a visited set [like the original algorithm suggests] or you will get only part of the paths. Also, you should limit paths to a certain length to avoid infinite loops [if the graph have cycles...]. Good Luck!

[amit]

@william007: Sure you can, but beware that you might get stuck in a cycle and stop yielding answers after a while. However - to get all simple paths from A to G - DFS is the way to go, and your visited set is per path (i.e. when you come back from the recursion, remove the element from the set before you continue to next node).

[william007]

@amit Hi, I have post a question （stackoverflow.com/q/14652724/1497720） related to this one here, hope you can help ：）

[boycy]

If I understand correctly, then that proof only works for undirected graphs, since in a directed graph the assertion that "this longest path has to traverse all vertices of G" does not necessarily hold. Is that right?

[araruna]

Well, yes, but you could use your algorithm to answer whether there is a directed hamiltonian path in a similar manner, which is also NP-complete. If your answer is n-1, then there is. If it is not, then there couldn't be such a path, or else it would be longer than your known longest.

[araruna]

Just to be clear. If the directed version could be solved in poly time, it's answer would give the answer to the Directed Hamiltonian Path. Moreover, if we had weighted edges, one can show that by a polynomial process we could answer the Traveling Salesman Problem.

[V Shreyas]

BFS can't find all possible paths in a graph containing cycles. Also, without keeping visited nodes, the code will run in a loop, and will never terminate. I guess the OP wanted to ask how to travel from A to B in paths without repetitive elements

[amit]

@VShreyas That's kinda old thread, the answer specifically says "all paths up to certain length", and that can be done with BFS without visited set. If you want to all simple paths between two nodes, you can do it with DFS with "local" visited set (that deletes a node from the visited set when it tracks back).

[arslan]

is there non-recursive version of this ?

[Omer Hassan]

I don't have one, no, but I think in theory, any recursive program can be converted into a non-recursive one, I think by using something like a stack object, the point being to emulate what a recursive program is actually doing using the program's stack space, I believe. You can look up the principle of converting recursive programs to non-recursive.

[Gareth Rees]

The k shortest paths can be found in polynomial time (even for graphs with loops) using an algorithm of David Eppstein. This problem is not NP-hard as claimed here.

[amit]

@GarethRees That's pseudo polynomial in k, not polynomial solution. However, I cannot find the reference for the problem being NP-Hard, so I removed this claim.

[amit]

@GarethRees Assume there is a polynomial time (NOT pseudo polynomial) algorithm for kth shortest simple path between two nodes. Since there are at most (3/2)n! such paths, you can do binary search and find if there is a simple path of length n. Since log{(3/2)n!} is polynomial in n, both encoding the number and the number of repeats needed is polynomial in input size. Since the algorithm runs in polynomial time as well for its input, the total run time is polynomial, and the answer is if there is a Hamiltonian Path between the nodes. Thus, if such algorithm exists, P=NP.

[amit]

@GarethRees Appendix: Number of paths, choose number of nodes in path (i=1,....,n), for each i, choose(n,i) nodes, and reorder them (i!), giving: (3/2)n!.

[hkBst]

If nodes can be visited multiple times, then the longest path is infinitely long. Thus a node can be visited at most once. If a node has only a single edge to the rest of the graph, then a path cannot both enter and exit that node, so that node cannot be part of any path and in particular not of the longest path. Of course you can exclude such nodes as part of your connected assumption, but perhaps you should make that clearer then.