how to find all possible path between 2 nodes
11 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Elysi Cochin
le 24 Avr 2019
Commenté : Ken Bannister
le 8 Avr 2023
knowing the connectivity between nodes, how can i find the possible path between 2 nodes?
2 commentaires
Ken Bannister
le 8 Avr 2023
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.
Réponse acceptée
Guillaume
le 24 Avr 2019
Modifié(e) : Guillaume
le 25 Avr 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
3 commentaires
Guillaume
le 25 Avr 2019
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.
Plus de réponses (1)
Voir également
Catégories
En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!