# 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.

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 CommentsShowHide 1 older comment
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.