The Dikstra shortest path algorithm on a weighted graph, directional or bidirectional, pretty quick. There is also the Bellman Ford algorithm. However, these two find the shortest path between one source to all vertices. However, if I only want to know the path between two vertices, is there a faster algorithm that only finds the distance between two nodes?
1
-
$\begingroup$ Sometimes you can run Dijkstra's algorithm from both ends at the same time. While it takes the same time on general graphs, for infinite tree, for example, it will take the square root of the time (assuming a near-constant branching factor) $\endgroup$– Command MasterFeb 4 at 14:22
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
Nope. The best you can do is to use Dijkstra's or Bellman-Ford. With Dijkstra's algorithm, you can stop the iteration as soon as you reach the target node, but this doesn't improve the worst-case asymptotic running time.
$\begingroup$
$\endgroup$
Dijkstra's is the asymptotically fastest possible for arbitrarily graphs we know nothing about, but most graphs in the real world have some sort of structure.
For example, A* is (usually) faster, but it requires a heuristic. Jump point search only works on fairly open grids, but for those cases it's an order-of-magnitude faster.
To tell you if there's a faster algorithm, we'd need to know more about your specific problem.
answered Apr 5, 2020 at 11:23
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
1,5091 gold badge10 silver badges16 bronze badges
$\begingroup$
$\endgroup$
What you are looking for are Point-to-Point Shortest Path Algorithms, which are often needed in finding the shortest paths in street networks. I am speculating here about you specific problem. In this context the graphs are planar and have some sort of structure we can use.
The A* algorithm is the most prominent one using some heuristic, such as the euclidean distance to limit the search space. However, we can do even better if we allow some kind of preprocessing of the graph.
One approach is using landmarks to improve the heuristic of the A*. Another is Transit node routing to precompute certain often used paths (such as highways) A third would be Arc Routing, which adds information to the edges, which the shortest path algorithms can use.
A more recent overview in german can be found here alongside some experimental evaluation at the end
