MATLAB built-in function to retrieve all possible paths between two nodes

3 次查看（过去 30 天）
Mohammad Ammar Bharmal
评论： Walter Roberson 2019-7-8
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
Walter Roberson 2019-7-8
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
Mohammad Ammar Bharmal 2019-7-8
I am basically trying to find all possible paths that meet a set of contiontions from the set of all paths between two nodes. To elaborate:
  1. Find all paths between two nodes in a graph
  2. Shortlist those paths which meet a certain criteria.
  3. Choose the shortest path from the shortlisted paths.
Walter Roberson
Walter Roberson 2019-7-8
https://www.mathworks.com/matlabcentral/answers/286462-how-to-find-all-possible-paths-from-one-node-to-another-node#answer_223872
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 个）

类别

在 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!

Translated by