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