0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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