how to find all possible path between 2 nodes

knowing the connectivity between nodes, how can i find the possible path between 2 nodes?

[Ken Bannister]

An interesting variation on this question is how to find the shortest path to visit each node just once. I suppose in this case one would have to loop through, using each node as a starting point.

[Ken Bannister]

Sppose further that for some reason one or more nodes are blocked?

Answer 1

[Guillaume]

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]

sir as you said i got the duplicate error

but when i did

edges = unique(edges);

that error went, but now another error showing,

what should i do to rectify the error? i'm using version 2016a

[Guillaume]

The duplicate issue I mention has nothing to do with duplicate edges when constructing the graph. My code will generate duplicates of the paths between the two nodes. E.g. with the graph:

g = digraph([1 2 3 4 4 1 7 3], [2 3 4 5 6 7 4 8]);
plot(g); %to visualise the graph

getallpaths will return:

allpaths = {[1 2 3 4 5],
            [1 7 4 5],
            [1 2 3 4 6],
            [1 7 4 6],
            [1 2 3 8]};

If you want all the paths between 1 and 4, after pruning, you'll get

selectedpaths = {[1 2 3 4],
                 [1 7 4],
                 [1 2 3 4],
                 [1 7 4]}

The 'duplicate edges not supported error' you get is probably specific to R2016b. Newer versions of matlab have no problem creating digraphs with duplicate edges. I have no idea in which version that support was added.

As for the error 'Undefined function 'full' for input arguments of type 'cell'' it would appear that I use an undocumented feature of ndgrid which support cell arrays in newer versions of matlab. Attached is a new version that doesn't use this undocumented feature and thus should work in your version.

[Elysi Cochin]

thank you Guillaume sir, now when i changed to the new getpaths function its working perfectly

Answer 2

[Walter Roberson]

https://www.mathworks.com/matlabcentral/answers/417396-calculating-all-paths-from-a-given-node-in-a-digraph#answer_335365

https://www.mathworks.com/matlabcentral/answers/171277-how-can-i-get-all-paths-between-two-nodes#answer_165813

[Elysi Cochin]

the input g is it the connectivity matrix like

[1,2;1,5;2,3;2,3;2,14;2,18;3,16;5,6;5,14;5,15]

is it correct?

[Walter Roberson]

https://www.mathworks.com/help/matlab/ref/digraph.toposort.html

[Guillaume]

toposort does not give you all paths between two nodes. It only gives you an ordering that makes searching the graph easier.

You could use my algorithm in Walter's first link to compute all paths of the graph, then only keep the paths that contain the two nodes you care about and finally remove duplicate leftovers. Although it would work, it wouldn't be particularly efficient since you'll be computing a lot of useless paths. You could probably solve your problem using bfsearch or dfsearch.

Using getpaths from my answer here:

%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(allpath));
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'

[Elysi Cochin]

thank you Guillaume sir, this was exactly what i wanted, please can you post it as an answer, so that i can accept it

[navanit dubey]

https://in.mathworks.com/matlabcentral/answers/650538-how-to-find-kshortest-path-or-use-dijkstra-algorithm-for-12-plot-points?s_tid=srchtitle

please tell me