I saw this question come up in the Gurubase analytics, and thought it’s worth discussing here:
How to find the shortest path to a single target vertex?
The simple answer is: To achieve good performance, always find shortest paths from a vertex, not to a vertex. If your graph is directed, use the mode parameter to treat edges as reversed.
Most algorithms for finding shortest paths compute path from a single vertex to all other vertices (single-source shortest path, SSSP). This means that even if you are looking for a path between a single source and single target, paths to all targets will be computed. When multiple sources are included, an SSSP computation will be done for each one. The implication is that the fewer sources are given, the faster the computation finishes. If you have few sources and many targets, swap sources/targets and treat edges are reversed (mode = IN instead of mode = OUT). Finally, reverse each returned path.
Example in R:
> library(igraph)
> set.seed(1234)
> g <- sample_gnm(10000, 50000, directed = T)
> system.time(distances(g, v = V(g), to = 1))
user system elapsed
2.051 0.004 2.055
> system.time(distances(g, v = 1, to = V(g), mode = "in"))
user system elapsed
0.003 0.000 0.004