0

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

Improve this question
2
  • 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.
    – Jules
    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.
    – Andreas
    Jul 24, 2018 at 10:43

1 Answer 1

Reset to default
2

I can't claim to have read it fully, but there's an algorithm by David Eppstein that appears to satisfy your requirements. A brief read suggests that it builds a tree of possible branching choices in a graph along with a shortest path generated by a traditional algorithm, and then provides a fast method to produce additional paths using the tree.

I haven't investigated the possibility further, but given that your graph seems pretty regular, it may well be that you can improve performance beyond this by the use of heuristics to narrow the search area (e.g. using something similar to the A* search algorithm).

Improve this answer
1
  • looks good. way to complex to implement within a days work (if I do it myself), and I couldn't find any trustworthy implementation this side of the millenia, so it looks like I'll have to make an effort at some point. like you say, given the graph is regular I can probably use heuristics to narrow the search
    – Andreas
    Jul 24, 2018 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.