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?

Answer 1

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.

Answer 2

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.

Answer 3

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)

Answer 4

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.