I'm a beginner in graph algorithm, and I have trouble to find an efficient solution for my issue.
My goal is to find X best paths between two vertices. Not only the shortest paths, but sub optimals path, ordered by length. My graph is relatively small (10k vertices, 20k edges) and is not directed. I don't use weight or vertices/edges attributes.
My current prototype: I use first all_shortest_paths to find the best paths. Then I use all_paths with a cutoff = length of shortest_path + K . K is an arbitrary value set as an argument of my function. Finally, I sort the return of all_paths by path length and select the X shortest.
It works fine when the vertices are close to each other, but when my cutoff is over 20ish, the all_paths function take forever and my CPU usage skyrockets. I can't even iterate with next() over the result. I understand that all_paths is not very effective in my case, but at the moment this is my best guess.
I'm reading the documentation of graph tools, but I cant find any other function fitting my needs. I 'm considering using the function bfs_search with a custom BFSVisitor, but I'm afraid i will encounter performance issues too.
Am i missing something?
Anyways, thanks for this library, its impressive. Sorry for my poor English.
-- Sent from: https://nabble.skewed.de/
Am 15.12.20 um 16:22 schrieb Ruhm:
My goal is to find X best paths between two vertices. Not only the shortest paths, but sub optimals path, ordered by length.
Finding the k-shortest paths is not yet implemented in graph-tool. You can see a simple version of the algorithm here:
If you open an issue in the website with a feature request, I will implement it when I find the time.