# shortest path between two vertices in a graph

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.

• please read this : en.wikipedia.org/wiki/Shortest_path_problem ,thank you, – IDOK Sep 7 '11 at 15:57
• Have you checked Topcoder tutorial on graph theory? – Quixotic Sep 7 '11 at 15:57
• As far as I know, no. At least in the worst case, all known algorithms do the same work, whether for finding shortest paths to a single target, or for shortest paths for all targets. (There were some typos in the previous comment, so I deleted it.) – Srivatsan Sep 7 '11 at 16:24
• As mentioned in the article iyengar linked to, the 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 as TonyK describes is a good alternative. – Rahul Sep 7 '11 at 16:51

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.
• @Anderson: Both. For a directed graph, just go backwards from $v$. – TonyK Oct 16 '12 at 17:32