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.

Answer 1

[Walter Roberson]

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

[Mohammad Ammar Bharmal]

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]

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.