All possible paths in a cyclic undirected graph

Question

I'm trying to develop an algorithm that identifies all possible paths between two nodes in a graph, as in this example:

.

in fact, i just need to know which nodes appear in all existing paths.

in the web only got references about DFS, A* or dijkstra, but i think they doesn't work in this case.

Does anyone know how to solve it?

won't there be an infinite number of paths if the graph is cyclic? — jalf, Jun 18 '10 at 00:31
@jalf, I thought so too, but Wikipedia says there is some disagreement. "A path with no repeated vertices is called a simple path, and a cycle with no repeated vertices or edges aside from the necessary repetition of the start and end vertex is a simple cycle. In modern graph theory, most often 'simple' is implied; i.e., 'cycle' means 'simple cycle' and 'path' means 'simple path', but this convention is not always observed, especially in applied graph theory." — Doug McClean, Jun 18 '10 at 00:38

score 5 · Accepted Answer · answered Jun 17 '10 at 07:03

You can find all paths using DFS like |Vlad described. To find which nodes appear in every path, you could just maintain an array of booleans that says whether each node has appeared in every path so far. When your DFS finds a path, go through each vertex not in the path and set the corresponding array value to false. When you are done, only the vertices with values of true will be the ones that appear in every path.

Pseudocode:

int source;
int sink;
int nVerts;
bool inAllPaths[nVerts]; // init to all true
bool visited[nVerts]; // init to all false
stack<int> path; // init empty

bool dfs(int u)
  if (visited[u])
    return;
  if (u == sink)
    for i = 0 to nVerts-1
      if !stack.contains(i)
        inAllPaths[i] = false;
    return true;
  else
    visited[u] = true;
    stack.push(u);
    foreach edge (u, v)
      dfs(v);
    stack.pop();
    visited[u] = false;
    return false;


main()
  dfs(source);
  // inAllPaths contains true at vertices that exist in all paths
  // from source to sink.

However, this algorithm isn't very efficient. For example, in a complete graph of n vertices (all vertices have edges to all others) the number of paths will be n! (n factorial).

A better algorithm would be to check for the existence in every path of each vertex separately. For each vertex, try to find a path from the source to the sink without going to that vertex. If you can't find one, that's because the vertex appears in every path.

Pseudocode:

// Using the same initialisation as above, but with a slight modification
// to dfs: change the foreach loop to
foreach edge (u, v)
  if (dfs(v))
    return true; // exit as soon as we find a path

main()
  for i = 0 to nVerts-1
    set all visited to false;
    if (inAllPaths[i])
      visited[i] = true;
      if (dfs(source))
        inAllPaths[i] = false;
      visited[i] = false;

Unfortunately, this still has exponential worst case when searching for a path. You can fix this by changing the search to a breadth-first search. If I'm not mistaken, this should give you O(VE) performance.

gaps96 · Answer 2 · 2012-12-07T22:12:42.833

I know it's been a while, but I came here looking for some algorithm to find All Paths (not only the shortest path) in SQL or Java and I found this three (I just post them to keep concepts organized):

Java

http://introcs.cs.princeton.edu/java/45graph/AllPaths.java.html (dependencies: Graph, ST, Set, In, are found in http://introcs.cs.princeton.edu/java/45graph/)
SQL (PostgreSQL).

Check WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS

http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-sql-meets-social-networks/

PL/SQL (Oracle)

https://forums.oracle.com/forums/thread.jspa?threadID=2415733

select pth as "Path", distance as "Distance"
from (
  select connect_by_root(n1) || sys_connect_by_path(n2,'>') pth ,n2, level as distance
  from -- Edge List Table
    (select 'A' n1,'B' n2 from dual
    union all select 'A','C' from dual
    union all select 'B','C' from dual
    union all select 'B','D' from dual
    union all select 'D','G' from dual
    union all select 'C','G' from dual
    union all select 'D','I' from dual
    union all select 'C','E' from dual
    union all select 'E','F' from dual
    union all select 'F','G' from dual
    union all select 'F','H' from dual   
    ) links
  start with n1='A'
  connect by nocycle prior n2=n1)
  where n2 = 'G';

Result:

Distance    Path
3   A>B>C>G
5   A>B>C>E>F>G
3   A>B>D>G
2   A>C>G
4   A>C>E>F>G

If you put in comments the lines start with n1... and where n2... the query will return all paths in all the graph.

score 1 · Answer 3 · answered Jun 17 '10 at 05:40

Run DFS from your start node and keep your own stack that tells you what nodes you've seen at any given time. Take care of cycles: when you've seen a node twice, you have a cycle and you have to abort your current path. Take care not to visit a node's parent, so as to avoid cycles of length 1 (add a parent parameter to your DFS function, it will help).

Then, when you reach the destination node, output the contents of your stack.

Once DFS finishes, you will have all the paths.

Ryan · Answer 4 · 2010-06-17T15:37:33.570

For this problem I would first get the tree t formed from a DFS on one of your target nodes u. Then, color all the nodes, lets say blue, that are in the subtree s rooted at your second target node v.

For each node k in subtree s, 
    if k has an edge to a non-blue node x 
    then k is true and x is true.

Also, mark v as true. Finally, I would use a recursive function down to the leaves. Something like

function(node n){
    if(n = null)
        return false
    if(function(n.left) or function(n.right) or n.val){
        n.val = true
        return true
    }
    else
        return false
}

All nodes marked as true would be your nodes in the paths from u to v. runtime would be at most (Vertices + Edges) since DFS = (V+E) the for loops at most (V) the recursive at most (V)

score 0 · Answer 5 · answered Jun 17 '10 at 23:59

a vertex is on a path from A to B if it's reachable from A, and B is reachable from it.

So: do a flood-fill starting from A. Mark all those vertices. do a flood-fill starting from B and following edges in reverse. All marked vertices you meet are part of the solution.

All possible paths in a cyclic undirected graph

5 Answers5

Linked