# how to find all possible path between 2 nodes

45 views (last 30 days)
Elysi Cochin on 24 Apr 2019
Commented: navanit dubey on 19 Nov 2020
knowing the connectivity between nodes, how can i find the possible path between 2 nodes?

Guillaume on 24 Apr 2019
Edited: Guillaume on 25 Apr 2019
Here is the code I posted as a comment to Walter's answer, it requires this function from my answer to another question:
%g: a DAG created with the digraph function
%s: start node
%e: end node
%eg:
edges = [1,2;1,5;2,3;2,3;2,14;2,18;3,16;5,6;5,14;5,15];
g = digraph(edges(:, 1), edges(:, 2));
s = 1;
e = 14;
%get all paths
allpaths = getpaths(g);
%only keep those paths that link s and e and only that part of the path between s and e (or e and s)
keep = false(size(allpaths));
for pidx = 1:numel(allpaths)
[found, where] = ismember([s, e], allpaths{pidx});
if all(found)
keep(pidx) = true;
allpaths{pidx} = allpaths{pidx}(min(where):max(where)); %only keep part of the path between the two node
end
end
selectedpaths = allpaths(keep)
%after pruning the path, we may have duplicates that need removing
%this part left as 'an exercice to the reader'
Note that as said, it's not the most efficient (and you still have to implement the duplicate removal). You probably can implement a more efficient algorithm using depth first or breadth first search.
edit: fixed a typo in a variable
Elysi Cochin on 25 Apr 2019
thank you Guillaume sir, now when i changed to the new getpaths function its working perfectly

Walter Roberson on 24 Apr 2019