MATLAB built-in function to retrieve all possible paths between two nodes
显示 更早的评论
Hi.
I am working with directed graphs. My graphs are really big and comprise of around 10,000 edges. I want to know MATLAB built-in function to retrieve all possible paths between two nodes.
Please guide me how to do that.
Thank you.
采纳的回答
Walter Roberson
2019-7-8
0 个投票
There is no built-in function for that purpose.
Are you trying to compute centrality?
https://www.mathworks.com/help/matlab/ref/graph.centrality.html
2 个评论
Mohammad Ammar Bharmal
2019-7-8
Walter Roberson
2019-7-8
All paths on a graph with 10000 edges is unlikely to be feasible, especially if there are loops.
The general approach that would typically used for that kind of problem is to do a breadth-first search:
- keep an array of current positions, an array of partial paths. At any one time at the N'th step, this represents all of the destinations that are N steps away
- prune paths as early as possible: as soon as you discover a path cannot meet the criteria, discard it
- at each step, go through all of the partial paths and for each add all of the possible next steps into the consideration list
- at some point you will reach the destination. If the criteria is not met then discard the path. If the criteria is met, set a flag indicating you have a solution, but keep processing through the rest of the current set, because you might find additional solutions that are the same length.
- At the end of considering all of the possibilities that are a certain number of steps away, if you have a solution, quit looking: you will not be able to find a shorter path if you keep looking.
更多回答（0 个）
类别
在 帮助中心 和 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!
Translated by 
