-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.

| cite | improve this question | | | | |
$\endgroup$
  • 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$.

| cite | improve this answer | | | | |
$\endgroup$

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