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

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.