An easy to understand (but efficient) algorithm to know the nodes which are in any path from a to b

Today I had to face a simple but interesting graph problem: Given a graph and two nodes a and b. Find all the nodes which form part of any of the possible paths from a to b.

Though it may seem a bit difficult for starters it can be solved easily using a simple algorithm and knowing a few things:

First we take the graph G and find the reverse graph G’ (this is a Graph with the edges reversed).

This would be the transposition of the connection matrix or could be done easily if the graph is represented as a vector of lists of nodes with a edge from its position going over each position on the vector and adding that position to the list on G’ on the position of every node in that list.

Now we will take a list L of all the nodes on G which are reachable from A. This can be easily done:

Q := queue
V :- bool vector size nodes(G) initialized to false
V[A] = True
Q.insert A
While ! Q.empty

n = Q.top
Q.pop
Foreach Q.edgeFrom(n) e #This is for each node with an edge from n to it

If (!V[e])

Q.insert n
V[e] = True

Then V will be True for each node reachable from A

We do the same with G’ and B and store it on L’

Finally if a node is in both L and L’ then it is part of at least one path from A to B

Now the explanation on why it works:

• If n is connected in G to A then there is at least one path P1 from A to n
• If n is connected in G’ to B then there is at least one path P2 from B to n
• As G’ is G with its edges reversed then the reverse of P2, P2” will be the path from n to B on G
• As there is a path from A to n and another from n to B then n is part of the path P1,n,P2′ which is a path from A to B so n is in at least one path from A to B

Finally to Big O calculation of its costs:

The cost of finding G’ is either O(N²) (If the graph is represented as a matrix whereh M[i,j] is 1 if there is a edge from i to j) or O(N+E) (If the graph is presented as a vector of lists of nodes reachable from i)

The cost of reachability is either O(N²) in the first case or O(N+E) on the second.

So the cost of this algorithm is either O(N²) or O(N+E) depending on the representation.