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.

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

1 Answer 1

1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .