Find all paths between two graph nodes

Question

I am working on an implemtation of Dijkstras Algorithm to retrieve the shortest path between interconnected nodes on a network of routes  I have the implentation 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

User · Answer

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 lt -0 to n       if i lt i0           C i  lt -0    there is no path from vertex ordered on the left from  s  after the topological sort       if i  i0          C i  lt -1       for j lt -0 to Adj i            C i  lt - C i  C j    return C i1

User · Answer

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

User · Answer

find paths s  t  d  k   This question is now a bit old    but I ll throw my hat into the ring   I personally find an algorithm of the form find paths s  t  d  k  useful  where    s is the starting node t is the target node d is the maximum depth to search k is the number of paths to find   Using your programming language s form of infinity for d and k will give you all paths        obviously if you are using a directed graph and you want all undirected paths between s and t you will have to run this both ways   find paths s  t  d  k   lt join gt  find paths t  s  d  k      Helper Function  I personally like recursion  although it can difficult some times  anyway first lets define our helper function   def find paths recursion graph  current  goal  current depth  max depth  num paths  current path  paths found    current path append current     if current depth  gt  max depth      return    if current    goal      if len paths found   lt   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  With that out of the way  the core 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  lets notice a few thing    the above pseudo-code is a mash-up of languages - but most strongly resembling python  since I was just coding in it   A strict copy-paste will not work     is an uninitialized list  replace this with the equivalent for your programming language of choice paths found is passed by reference  It is clear that the recursion function doesn t return anything  Handle this appropriately  here graph is assuming some form of hashed structure  There are a plethora of ways to implement a graph  Either way  graph vertex  gets you a list of adjacent vertices in a directed graph - adjust accordingly  this assumes you have pre-processed to remove  buckles   self-loops    cycles and multi-edges

User · Answer

You usually don t want to  because there is an exponential number of them in nontrivial graphs  if you really want to get all  simple  paths  or all  simple  cycles  you just find one  by walking the graph   then backtrack to another

User · Answer

If you actually care about ordering your paths from shortest path to longest path then it would be far better to use a modified A  or Dijkstra Algorithm  With a slight modification the algorithm will return as many of the possible paths as you want in order of shortest path first  So if what you really want are all possible paths ordered from shortest to longest then this is the way to go   If you want an A  based implementation capable of returning all paths ordered from the shortest to the longest  the following will accomplish that  It has several advantages  First off it is efficient at sorting from shortest to longest  Also it computes each additional path only when needed  so if you stop early because you dont need every single path you save some processing time  It also reuses data for subsequent paths each time it calculates the next path so it is more efficient  Finally if you find some desired path you can abort early saving some computation time  Overall this should be the most efficient algorithm if you care about sorting by path length   import java util     public class AstarSearch       private final Map lt Integer  Set lt Neighbor gt  gt  adjacency      private final int destination       private final NavigableSet lt Step gt  pending   new TreeSet lt  gt          public AstarSearch Map lt Integer  Set lt Neighbor gt  gt  adjacency  int source  int destination            this adjacency   adjacency          this destination   destination           this pending add new Step source  null  0               public List lt Integer gt  nextShortestPath             Step current   this pending pollFirst            while  current    null                if  current getId      this destination                   return current generatePath                for  Neighbor neighbor   this adjacency get current id                     if  current seen neighbor getId                           final Step nextStep   new Step neighbor getId    current  current cost   neighbor cost   predictCost neighbor id  this destination                        this pending add nextStep                                               current   this pending pollFirst                      return null             protected int predictCost int source  int destination            return 0    Behaves identical to Dijkstra s algorithm  override to make it A             private static class Step implements Comparable lt Step gt            final int id          final Step parent          final int cost           public Step int id  Step parent  int cost                this id   id              this parent   parent              this cost   cost                     public int getId                 return id                     public Step getParent                 return parent                     public int getCost                 return cost                     public boolean seen int node                if this id    node                  return true              else if parent    null                  return false              else                 return this parent seen node                      public List lt Integer gt  generatePath                 final List lt Integer gt  path              if this parent    null                  path   this parent generatePath                else                 path   new ArrayList lt  gt                 path add this id               return path                      Override         public int compareTo Step step                if step    null                  return 1              if  this cost    step cost                  return Integer compare this cost  step cost               if  this id    step id                   return Integer compare this id  step id               if  this parent    null                   this parent compareTo step parent               if step parent    null                  return 0              return -1                      Override         public boolean equals Object o                if  this    o  return true              if  o    null    getClass      o getClass    return false              Step step    Step  o              return id    step id  amp  amp                  cost    step cost  amp  amp                  Objects equals parent  step parent                       Override         public int hashCode                 return Objects hash id  parent  cost                                                                                       Everything below here just sets up your adjacency           It will just be helpful for you to be able to test          It isnt part of the actual A  search algorithm                                                                         private static class Neighbor           final int id          final int cost           public Neighbor int id  int cost                this id   id              this cost   cost                     public int getId                 return id                     public int getCost                 return cost                       public static void main String   args            final Map lt Integer  Set lt Neighbor gt  gt  adjacency   createAdjacency            final AstarSearch search   new AstarSearch adjacency  1  4           System out println  printing all paths from shortest to longest               List lt Integer gt  path   search nextShortestPath            while path    null                System out println path               path   search nextShortestPath                         private static Map lt Integer  Set lt Neighbor gt  gt  createAdjacency             final Map lt Integer  Set lt Neighbor gt  gt  adjacency   new HashMap lt  gt                This sets up the adjacencies  In this case all adjacencies have a cost of 1  but they dont need to          addAdjacency adjacency  1 2 1 5 1              1   2 5          addAdjacency adjacency  2 1 1 3 1 4 1 5 1      2   1 3 4 5          addAdjacency adjacency  3 2 1 5 1              3   2 5          addAdjacency adjacency  4 2 1                  4   2          addAdjacency adjacency  5 1 1 2 1 3 1          5   1 2 3           return Collections unmodifiableMap adjacency              private static void addAdjacency Map lt Integer  Set lt Neighbor gt  gt  adjacency  int source  Integer    dests            if  dests length   2    0              throw new IllegalArgumentException  dests must have an equal number of arguments  each pair is the id and cost for that traversal             final Set lt Neighbor gt  destinations   new HashSet lt  gt             for int i   0  i  lt  dests length  i  2              destinations add new Neighbor dests i   dests i 1             adjacency put source  Collections unmodifiableSet destinations              The output from the above code is the following    1  2  4   1  5  2  4   1  5  3  2  4    Notice that each time you call nextShortestPath   it generates the next shortest path for you on demand  It only calculates the extra steps needed and doesnt traverse any old paths twice  Moreover if you decide you dont need all the paths and end execution early you ve saved yourself considerable computation time  You only compute up to the number of paths you need and no more   Finally it should be noted that the A  and Dijkstra algorithms do have some minor limitations  though I dont think it would effect you  Namely it will not work right on a graph that has negative weights   Here is a link to JDoodle where you can run the code yourself in the browser and see it working  You can also change around the graph to show it works on other graphs as well  http   jdoodle com a ukx

User · Answer

I think what you want is some form of the Ford   Fulkerson algorithm which is based on BFS   Its used to calculate the max flow of a network  by finding all augmenting paths between two nodes   http   en wikipedia org wiki Ford E2 80 93Fulkerson algorithm

User · Answer

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

User · Answer

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 lt Stack gt  connectionPaths   new ArrayList lt  gt        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

User · Answer

I suppose you want to find  simple  paths  a path is simple if no node appears in it more than  once  except maybe the 1st and the last one    Since the problem is NP-hard  you might want to do a variant of depth-first search   Basically  generate all possible paths from A and check whether they end up in G

User · Answer

There s a nice article which may answer your question  only it prints the paths instead of collecting them   Please note that you can experiment with the C   Python samples in the online IDE   http   www geeksforgeeks org find-paths-given-source-destination

User · Answer

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

[algorithm] Find all paths between two graph nodes

Examples related to algorithm

Examples related to graph-theory

Examples related to graph-algorithm

Examples related to breadth-first-search