how to find all possible path between 2 nodes
13 次查看(过去 30 天)
显示 更早的评论
knowing the connectivity between nodes, how can i find the possible path between 2 nodes?
2 个评论
Ken Bannister
2023-4-8
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.
采纳的回答
Guillaume
2019-4-24
编辑:Guillaume
2019-4-25
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 个评论
Guillaume
2019-4-25
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.
更多回答(1 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!