# Which graph algorithm should I use?

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

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

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.