how to find all possible path between 2 nodes
11 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Elysi Cochin
el 24 de Abr. de 2019
Comentada: Ken Bannister
el 8 de Abr. de 2023
knowing the connectivity between nodes, how can i find the possible path between 2 nodes?
2 comentarios
Ken Bannister
el 8 de Abr. de 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.
Ken Bannister
el 8 de Abr. de 2023
Sppose further that for some reason one or more nodes are blocked?
Respuesta aceptada
Guillaume
el 24 de Abr. de 2019
Editada: Guillaume
el 25 de Abr. de 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 comentarios
Guillaume
el 25 de Abr. de 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.
Más respuestas (1)
Ver también
Categorías
Más información sobre Graph and Network Algorithms en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!