how to find all possible path between 2 nodes

35 views (last 30 days)
knowing the connectivity between nodes, how can i find the possible path between 2 nodes?

Accepted Answer

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
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
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
Elysi Cochin on 25 Apr 2019
Edited: Elysi Cochin on 25 Apr 2019
thank you Guillaume sir, now when i changed to the new getpaths function its working perfectly

Sign in to comment.

More Answers (1)

Walter Roberson
Walter Roberson on 24 Apr 2019

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!