What's the best algorithm to find the shortest path between 2 vertices in a graph?

Question

Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?

Answer 1

At least in theory, the most appropriate algorithm is breadth-first search (BFS), which you execute by starting from your source vertex $s$. Once the BFS traversal hits your target vertex $t$, you halt and trace back a chain of predecessors originating from $t$. This procedure runs in linear time, which is optimal.

However, from a practical standpoint, the answer might depend on the topology of your graph. For instance, some other linear time procedure like a bidirectional search can be much more efficient but this is more challenging to determine apriori.

Answer 2

As Juho already mentioned, Breadth First Search is a good choice but whether it is or not the most appropriate algorithm depends upon other factors. In the following I'm assuming that your graph $G(V, E)$ has been given explicitly, and that two vertices $s, t\in V$ are also known upfront.

First, note that Breadth First Search requires an amount of memory which is linear in the size of the graph and this restricts is applicability in most real-world cases. Since you are considering an unweighted/undirected graph then Bidirectional Breadth-First search is for sure much better than its unidirectional counterpart, as it lowers down the memory requirements from $O(bˆd)$ to $O(bˆ\frac{d}{2})$, with $d$ being the depth of the optimal solution (in your case, the number of steps required to get from one vertex to another) and $b$ the branching factor, or average number of descendants.

However, even so this algorithm might exhaust the available memory. If that is the case then you should consider depth-first search strategies. As you are interested in computing optimal solutions then you should consider either Iterative Deepening or Depth-First Branch-and-Bound. The latter is particularly well-suited for those cases where all solutions lie at the same depth (such as in permutation state spaces) which, most likely, is not your case; the former simply launches a number of depth-first searches incrementing the depth by one in each iteration and starting always from scratch until a solution is found. As the threshold was incremented by one in every iteration, the solution found has to be optimal.

However, depth-first strategies suffer severily from transpositions: if there are various paths to get from the start state to another node $n$, these algorithms re-expand $n$ as many times as necessary whereas breadth-first search strategies can avoid re-expansions.

In a nutshell:

• If you have memory enough then I recommend you bidirectional breadth-first search.
• If not, then consider iterative-deepening unless you have a large number of transpositions

In case you have not memory enough for running the first algorithm and you have many transpositions, then you should move to heuristic search algorithms.

Hope this helps,

Answer 3

You can search from both ends. Find the vertices one step away from X, one step from Y, 2 steps from X, two steps from Y, and so on, until you find a set with a common vertex.