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$
2
  • $\begingroup$ THere are many algorithms you could use. Without more information, there's no way to answer your question. $\endgroup$ Jun 1, 2017 at 8:20
  • $\begingroup$ I've added some info about what am doing $\endgroup$
    – PROW
    Jun 1, 2017 at 18:25

2 Answers 2

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$
1
  • $\begingroup$ Thanks, I have implemented the algorithm and I got a speed up of 870 in my graph. $\endgroup$
    – PROW
    Jun 3, 2017 at 19:03
4
$\begingroup$

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

$\endgroup$
0

Your Answer

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

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