Path between 2 nodes in a graph

How to check if a path exists between two nodes in a graph?

Answer 1

[Michael Croucher]

One way to proceed would be to use concomp.

Take this example graph

s = [1 2 2 3 3 3 4 5 5 5 8 8];
t = [2 3 4 1 4 5 5 3 6 7 9 10];
G = graph(s,t);
plot(G,'Layout','layered')

>> components=conncomp(G)
ans =
     1     1     1     1     1     1     1     2     2     2

We can see that there are two connected components. To see it nodes 4 and 7 are connected (for example), just see if they are members of the same component.

components(4)==components(7)
ans =
  logical
   1

[Hari]

This did work for me. Thanks

[Christine Tobler]

Note this works well for an undirected graph, but for directed graphs it would be more complicated: In that case, you'd want to look into digraph/transclosure to get connection between every pair of nodes.

Answer 2

[Christine Tobler]

Compute a path between the nodes, then check if the result is empty (this is returned by shortestpath if no path exists):

path = shortestpath(G, firstNode, secondNode)
pathExists = ~isempty(path);

[Hari]

Will this be computationally intensive if I need to check paths between every node pair (say there 100 nodes)?

[Bruno Luong]

Read Michael's answer that suggests using concomp