Return to Answer

Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.

Push s on the path stack and call search(s):

path // is a stack (initially empty)
seen // is a set

def stuck(x)
   if x == t
     return False
   for each neighbor y of x
     if y not in seen
       insert y in seen
       if !stuck(y)
         return False
   return True

def search(x)
  if x == t
    print path
    return
  seen = set(path)
  if stuck(x)
    return
  for each neighbor y of x
    if y not in seen:
      push y on the path
      search(y)
      pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.

Push s on the path stack and call search(s):

path // is a stack (initially empty)
seen // is a set

def stuck(x)
   if x == t
     return False
   for each neighbor y of x
     if y not in seen
       insert y in seen
       if !stuck(y)
         return False
   return True

def search(x)
  if x == t
    print path
    return
  seen = set(path)
  if stuck(x)
    return
  for each neighbor y of x
    if y not in path:
      push y on the path
      search(y)
      pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.

Push s on the path stack and call search(s):

path // is a stack (initially empty)
seen // is a set

def stuck(x)
   if x == t
     return False
   for each neighbor y of x
     if y not in seen
       insert y in seen
       if !stuck(y)
         return False
   return True

def search(x)
  if x == t
    print path
  seen = set(path)
  if stuck(x)
    return
  for each neighbor y of x
    push y on the path
    search(y)
    pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.

Push s on the path stack and call search(s):

path // is a stack (initially empty)
seen // is a set

def stuck(x)
   if x == t
     return False
   for each neighbor y of x
     if y not in seen
       insert y in seen
       if !stuck(y)
         return False
   return True

def search(x)
  if x == t
    print path
    return
  seen = set(path)
  if stuck(x)
    return
  for each neighbor y of x
    if y not in seen:
      push y on the path
      search(y)
      pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

As was mentioned, in a graph with n nodes (1) there could be n! paths and (2) if there are m paths, then DFS finds all in $O(mn)$ time. You may want to list only k shortest paths, where k is parameter you choose. In that case, see this article by Eppstein.

Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.

Push s on the path stack and call search(s):

path // is a stack (initially empty)
seen // is a set

def stuck(x)
   if x == t
     return False
   for each neighbor y of x
     if y not in seen
       insert y in seen
       if !stuck(y)
         return False
   return True

def search(x)
  if x == t
    print path
  seen = set(path)
  if stuck(x)
    return
  for each neighbor y of x
    push y on the path
    search(y)
    pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.