# Find nth best path in graph G from node A to node B (without loops)

I'm making an graph layout optimizer and need to find paths from node a to node b in graph g. It has gone pretty well so far, but I lack an algorithm to take the next step.

So far I've used BFS to find the best path from a to b. The next step would be to find all paths from a to b, without loops. Q: What algorithms can do this? Any CPU or GPU friendly algorithms are of interest.

Now to the tricky part; performance. Number of nodes are up to ~1000, and each connects to ~10 other nodes. Number of nodes in any path is often 4-5 nodes for the best path and ~15 for a bad path. The optimizer is used in an editor and so should complete a layout in less than a second. Because of how the optimizer works (BFS applied onto implicitly represented graph), we can assume the algorithm to be exercised maybe 10-100 times in a single pass. Basically, it has to be found in less than 10ms given those numbers. Platform is a high-end desktop having about that much memory.

Not all paths need be found immediately, and in fact very few are needed. The result could just as well be a tuple of the (n) best path, and the script generating the (n+1) best path, where (n) will rarely surpass 10 since the optimizer is very likely to have found an optimal solution before that. The script would then only be evaluated should the optimizer not have found a solution with cost lower than that of path (n).

• Finding all paths in a graph of that size is going to require a lot of memory, and is not going to be fast. You don't specify interconnectedness (which is hard to quantify), but in a network that size a random pair of nodes is likely to have at least many thousands of viable routes, with an average length of at least 100 nodes, which means even just enumerating them (assuming an algorithm can produce them with no actual work) is going to take a significant portion of a million steps. 10ms is not a plausible response time for this. It will take about twice that just in memory transfers. Commented Jul 24, 2018 at 9:16
• @Jules I edited the question to clarified that the optimizer will only need a few of the best paths from a to b. Path length is generally not very long either (edit pending) which should allow for solution to stay within reasonable resource limits. The network is not random at all, it is a grid where each cell is a node having axis aligned arcs to other nodes, unless there are obstacles. Commented Jul 24, 2018 at 10:43