Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
please read this : en.wikipedia.org/wiki/Shortest_path_problem ,thank you, –  Iyengar 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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
I see: en.wikipedia.org/wiki/Bidirectional_search –  stefan Sep 7 '11 at 18:10
    
Does this apply to directed graphs, or to undirected graphs? –  Anderson Green Oct 15 '12 at 19:02
    
@Anderson: Both. For a directed graph, just go backwards from $v$. –  TonyK Oct 16 '12 at 17:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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