3
$\begingroup$

I need to find the shortest path in a Directed Unweighted Cyclic graph. And it has to be optimal (find a path if exists one) and also optimal in terms of space and time complexity, being time complexity the most important. I think BFS is the solution. But am not sure.

What I am doing is mapping database tables into a graph data structure. And I need the shortest path for querying the tables with joins. Am storing information in the edges related to the nature of the relationship between the tables, like foreign key field and type of relation (one2many, one2one, etc).

$\endgroup$
  • $\begingroup$ THere are many algorithms you could use. Without more information, there's no way to answer your question. $\endgroup$ – David Richerby Jun 1 '17 at 8:20
  • $\begingroup$ I've added some info about what am doing $\endgroup$ – PROW Jun 1 '17 at 18:25
2
$\begingroup$

You can use bidirectional BFS. It will find a shortest path in an unweighted graph much faster than the traditional BFS.

The only additional requirement in using a bidirectional search is that you can efficiently compute the parent nodes of any given node.

If you ask why, the argument is simple: BFS runs in $\mathcal{O}(\sum_{ = 0}^N b^i)$, whereas the bidirectional BFS runs in $\mathcal{O}(2 \sum_{i = 0}^{\lceil N / 2 \rceil}b^i)$, where $b$ is the average node degree and $N$ is the length of a shortest path. So by carefully choosing the graph statistics, you can make bidirectional BFS arbitrarily faster than traditional BFS. Actually, twice I have seen a speed up of 1000.

$\endgroup$
  • $\begingroup$ Thanks, I have implemented the algorithm and I got a speed up of 870 in my graph. $\endgroup$ – PROW Jun 3 '17 at 19:03
4
$\begingroup$

Do you have any sort of distance-heuristic? If not, then yes, BFS is likely your best choice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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