MATLAB Answers

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

83 views (last 30 days)
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.

Accepted Answer

Walter Roberson
Walter Roberson on 8 Jul 2019
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 Comments
Walter Roberson
Walter Roberson on 8 Jul 2019
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.

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!