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?


  • 2
    $\begingroup$ please read this : en.wikipedia.org/wiki/Shortest_path_problem ,thank you, $\endgroup$ – IDOK Sep 7 '11 at 15:57
  • $\begingroup$ Have you checked Topcoder tutorial on graph theory? $\endgroup$ – Quixotic Sep 7 '11 at 15:57
  • $\begingroup$ 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.) $\endgroup$ – Srivatsan Sep 7 '11 at 16:24
  • $\begingroup$ 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. $\endgroup$ – 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.

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

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.