Find the paths between two given nodes

Question

Say I have nodes connected in the below fashion  how do I arrive at the number of paths that exist between given points  and path details   1 2   node 1 and 2 are connected 2 3 2 5 4 2 5 11 11 12 6 7 5 6 3 6 6 8 8 10 8 9   Find the paths from 1 to 7    Answer  2 paths found and they are   1 2 3 6 7 1 2 5 6 7     implementation found here is nice I am going to use the same  Here is the snippet from the above link in python    a sample graph graph     A     B    C   E                  B     A   C    D                  C     D                  D     C                  E     F   D                  F     C     class MyQUEUE    just an implementation of a queue      def   init   self           self holder           def enqueue self val           self holder append val       def dequeue self           val   None         try              val   self holder 0              if len self holder     1                  self holder                  else                  self holder   self holder 1              except              pass          return val        def IsEmpty self           result   False         if len self holder     0              result   True         return result   path queue   MyQUEUE     now we make a queue   def BFS graph start end q        temp path    start       q enqueue temp path       while q IsEmpty      False          tmp path   q dequeue           last node   tmp path len tmp path -1          print tmp path         if last node    end              print  VALID PATH     tmp path         for link node in graph last node               if link node not in tmp path                   new path                      new path   tmp path    link node                  q enqueue new path   BFS graph  A   D  path queue   -------------results-------------------   A     A    B     A    C     A    E     A    B    C     A    B    D   VALID PATH      A    B    D     A    C    D   VALID PATH      A    C    D     A    E    F     A    E    D   VALID PATH      A    E    D     A    B    C    D   VALID PATH      A    B    C    D     A    E    F    C     A    E    F    C    D   VALID PATH      A    E    F    C    D

User · Answer

Dijkstra s algorithm applies more to weighted paths and it sounds like the poster was wanting to find all paths  not just the shortest   For this application  I d build a graph  your application sounds like it wouldn t need to be directed  and use your favorite search method  It sounds like you want all paths  not just a guess at the shortest one  so use a simple recursive algorithm of your choice   The only problem with this is if the graph can be cyclic   With the connections    1  2 1  3 2  3 2  4   While looking for a path from 1- 4  you could have a cycle of 1 -  2 -  3 -  1   In that case  then I d keep a stack as traversing the nodes  Here s a list with the steps for that graph and the resulting stack  sorry for the formatting - no table option    current node  possible next nodes minus where we came from   stack    1  2  3   1  2  3  4   1  2  3  1   1  2  3  1  2  3   1  2  3  1    error - duplicate number on the stack - cycle detected 3     1  2  3     back-stepped to node three and popped 1 off the stack  No more nodes to explore from here 2  4   1  2     back-stepped to node 2 and popped 1 off the stack  4     1  2  4     Target node found - record stack for a path  No more nodes to explore from here 2     1  2    back-stepped to node 2 and popped 4 off the stack  No more nodes to explore from here 1  3   1    back-stepped to node 1 and popped 2 off the stack  3  2   1  3  2  1  4   1  3  2  1  2  3   1  3  2  1    error - duplicate number on the stack - cycle detected 2  4   1  3  2    back-stepped to node 2 and popped 1 off the stack 4     1  3  2  4  Target node found - record stack for a path  No more nodes to explore from here 2     1  3  2    back-stepped to node 2 and popped 4 off the stack  No more nodes 3     1  3     back-stepped to node 3 and popped 2 off the stack  No more nodes 1     1     back-stepped to node 1 and popped 3 off the stack  No more nodes Done with 2 recorded paths of  1  2  4  and  1  3  2  4

User · Answer

The original code is a bit cumbersome and you might want to use the collections deque instead if you want to use BFS to find if a path exists between 2 points on the graph  Here is a quick solution I hacked up   Note  this method might continue infinitely if there exists no path between the two nodes  I haven t tested all cases  YMMV     from collections import deque    a sample graph   graph     A     B    C   E                B     A   C    D                C     D                D     C                E     F   D                F     C        def BFS start  end           Method to determine if a pair of vertices are connected using BFS      Args        start  end  vertices for the traversal       Returns         start  v1  v2      end              path          q   deque       q append start      while len q         tmp vertex   q popleft         if tmp vertex not in path          path append tmp vertex         if tmp vertex    end          return path        for vertex in graph tmp vertex           if vertex not in path            q append vertex

User · Answer

For those who are not PYTHON expert  the same code in C       Author  Ritesh Kumar Gupta  include  lt stdio h gt   include  lt vector gt   include  lt algorithm gt   include  lt vector gt   include  lt queue gt   include  lt iostream gt  using namespace std  vector lt vector lt int gt   gt GRAPH 100   inline void print path vector lt int gt path        cout lt  lt           for int i 0 i lt path size     i                cout lt  lt path i  lt  lt                cout lt  lt     lt  lt endl    bool isadjacency node not present in current path int node vector lt int gt path        for int i 0 i lt path size     i                if path i   node          return false            return true    int findpaths int source  int target  int totalnode int totaledge         vector lt int gt path      path push back source       queue lt vector lt int gt   gt q      q push path        while  q empty                  path q front            q pop             int last nodeof path path path size  -1           if last nodeof path  target                        cout lt  lt  The Required path is                  print path path                     else                       print path path                      for int i 0 i lt GRAPH last nodeof path  size     i                        if isadjacency node not present in current path GRAPH last nodeof path  i  path                                  vector lt int gt new path path begin   path end                     new path push back GRAPH last nodeof path  i                    q push new path                                         return 1    int main           freopen  out txt   w  stdout       int T N M u v source target      scanf   d   amp T       while T--                printf  Enter Total Nodes  amp  Total Edges n            scanf   d d   amp N  amp M           for int i 1 i lt  M   i                        scanf   d d   amp u  amp v               GRAPH u  push back v                     printf   Source  target  n            scanf   d d   amp source  amp target           findpaths source target N M               system  pause        return 0        Input   1 6 11 1 2  1 3 1 5 2 1 2 3 2 4 3 4 4 3 5 6 5 4 6 3 1 4  output    1     1 2     1 3     1 5     1 2 3   The Required path is     1 2 4   The Required path is     1 3 4     1 5 6   The Required path is     1 5 4   The Required path is     1 2 3 4     1 2 4 3     1 5 6 3     1 5 4 3   The Required path is     1 5 6 3 4

User · Answer

What you re trying to do is essentially to find a path between two vertices in a  directed   graph check out Dijkstra s algorithm if you need shortest path or write a simple recursive function if you need whatever paths exist

User · Answer

given the adjacency matrix    0  1  3  4  0  0    0  0  2  1  2  0    0  1  0  3  0  0    0  1  1  0  0  1    0  0  0  0  0  6    0  1  0  1  0  0   the following Wolfram Mathematica code solve the problem to find all the simple paths between two nodes of a graph  I used simple recursion  and two global var to keep track of cycles and to store the desired output   the code hasn t been optimized just for the sake of code clarity  the  print  should be helpful to clarify how it works   cycleQ l    If Length DeleteDuplicates l      Length l   False  True   getNode matrix   node    Complement Range Length matrix   Flatten Position matrix  node    0      builtTree node   matrix    Block  nodes  posAndNodes  root  pos       If  node         amp  amp  node    endNode           root   node          nodes   getNode matrix  node             Print  root   root  ---nodes   nodes              AppendTo lcycle  Flatten  root  nodes             If cycleQ lcycle     True              lcycle   Most lcycle   appendToTree root  nodes                Print  paths     tree    n    root    root   ---nodes   nodes               appendToTree root  nodes                       appendToTree root   nodes      Block  pos  toAdd       pos   Flatten Position tree  All  -1    root        For i   1  i  lt   Length pos   i            toAdd   Flatten Thread  tree  pos  i              amp     nodes             check cycles                        If cycleQ       True  AppendTo tree       amp     toAdd             tree   Delete tree       amp     pos       builtTree    matrix   amp     Union tree  All  -1                 to call the code      initNode   1      endNode   6      lcycle           tree     initNode        builtTree initNode  matrix    paths    1   root 1---nodes  2 3 4   paths    1 2   1 3   1 4   root 2---nodes  3 4 5   paths    1 3   1 4   1 2 3   1 2 4   1 2 5   root 3---nodes  2 4   paths    1 4   1 2 4   1 2 5   1 3 4   1 2 3 4   1 3 2 4   1 3 2 5   root 4---nodes  2 3 6   paths    1 2 5   1 3 2 5   1 4 6   1 2 4 6   1 3 4 6   1 2 3 4 6   1 3 2 4 6   1 4 2 5   1 3 4 2 5   1 4 3 2 5   root 5---nodes  6   RESULTS   1  4  6    1  2  4  6    1  2  5  6    1  3  4  6    1  2  3  4  6    1  3  2  4  6    1  3  2  5  6    1  4  2  5  6    1  3  4  2  5  6    1  4  3  2  5  6       Unfortunately I cannot upload images to show the results in a better way     http   textanddatamining blogspot com

User · Answer

In Prolog  specifically  SWI-Prolog    - use module library tabling       path  Graph  Source  Target  Path   - table path 4   path   N N  N    path G S T  S Path    -     dif S T       member S-I  G     directed graph     path G I T Path     test    paths  - Graph         1- 2    node 1 and 2 are connected       2- 3        2- 5        4- 2        5-11      11-12       6- 7        5- 6        3- 6        6- 8        8-10       8- 9            findall Path  path Graph 1 7 Path   Paths       maplist writeln  Paths     - paths   1 2 3 6 7   1 2 5 6 7  true

User · Answer

Breadth-first search traverses a graph and in fact finds all paths from a starting node  Usually  BFS doesn t keep all paths  however  Instead  it updates a prededecessor function p to save the shortest path  You can easily modify the algorithm so that p n  doesn t only store one predecessor but a list of possible predecessors   Then all possible paths are encoded in this function  and by traversing p recursively you get all possible path combinations   One good pseudocode which uses this notation can be found in Introduction to Algorithms by Cormen et al  and has subsequently been used in many University scripts on the subject  A Google search for    BFS pseudocode predecessor p    uproots this hit on Stack Exchange

User · Answer

If you want all the paths  use recursion   Using an adjacency list  preferably  create a function f   that attempts to fill in a current list of visited vertices  Like so   void allPaths vector lt int gt  previous  int current  int destination        previous push back current        if  current    destination            output all elements of previous  and return      for  int i   0  i  lt  neighbors current  size    i            allPaths previous  neighbors current  i   destination      int main              input     allPaths vector lt int gt     start  end       Due to the fact that the vector is passed by value  and thus any changes made further down in the recursive procedure aren t permanent   all possible combinations are enumerated   You can gain a bit of efficiency by passing the previous vector by reference  and thus not needing to copy the vector over and over again  but you ll have to make sure that things get popped back   manually   One more thing  if the graph has cycles  this won t work   I assume in this case you ll want to find all simple paths  then  Before adding something into the previous vector  first check if it s already in there   If you want all shortest paths  use Konrad s suggestion with this algorithm

[algorithm] Find the paths between two given nodes?

Examples related to algorithm

Examples related to path

Examples related to graph-theory

Examples related to pseudocode