2
$\begingroup$

I realize this is a very basic question, but I am amazed that I didn't find much useful information on the web:

Given a (directed/undirected) edge weighted graph G, and two of its vertices u,v, is there an algorithm which finds the shortest path from u and v.

Of course I can terminate any single-source shortest path algo (like Dijkstra) after node v has been processed, but are there any simpler algorithms, with better running time?

Thanks.

  • 0
    As mentioned in the article iyengar linked to, the [A* search algorithm](http://en.wikipedia.org/wiki/A*_search_algorithm) is a popular extension of Dijkstra's algorithm for finding the shortest path between two vertices. However, if you don't have a nice heuristic available, [bidirectional search](http://en.wikipedia.org/wiki/Bidirectional_search) as TonyK describes is a good alternative.2011-09-07

1 Answers 1

1

Suppose (to keep things simple) that all edges have weight $1$. Let $d$ be the distance from $u$ to $v$. Then a single-source shortest path algorithm will have to find all vertices at distance $< d$ from $u$ before it finds $v$ at distance $d$.
However, there is a slightly better way: execute two single-source shortest path algorithms, starting at $u$ and $v$, performing the iterations alternately. Stop when you find a vertex for which you know the shortest path from both $u$ and $v$. This algorithm only requires you to find all vertices at a distance of $\le d/2$ from $u$ or $v$, which is certainly no more work than the first algorithm, and may (depending on the properties of the graph) be much less work.

  • 0
    @Anderson: Both. For a directed graph, just go backwards from $v$.2012-10-16