-4
$\begingroup$

I'm developing a route planner, and I was reading some graph theory.

I read a little bit of Dijkstra's shortest path, shooting star and turn restrictions, and I tend to think that this algorithms are thought to be used for searching a short path between two nodes, node A and node B (or in some variant, edge A and edge B).

I was wondering if it's a variant of some shortest path algorithm to find the shortest path between two set of nodes. I could define this problem better like this:

Input:

  • Graph
  • List of initial nodes
  • List of end nodes

Output:

  • Node A
  • Node B
  • Shortest path

I can think of a trivial solution: "Take each of the 'initial nodes' apply dijkstra against each of the 'final nodes', select the minimal path from all returned paths", but I'm trying to find if exists some algorithm to solve this task.

$\endgroup$

closed as off topic by David Eppstein, arnab, Yuval Filmus, Mohammad Al-Turkistany, Jeffε Feb 24 '13 at 8:09

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ This does not appear to be a research-level question in theoretical computer science to me. $\endgroup$ – David Eppstein Feb 22 '13 at 22:41
11
$\begingroup$

Create a new node $s$ and connect it to every node in the first list.

Create a new node $t$ and connect it to every node in the second list.

Find a shortest path between $s$ and $t$.

$\endgroup$

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