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

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

<p>Find a shortest path between $s$ and $t$.</p>

CC BY-SA 3.0
2013-02-22T21:55:42.487Z
2013-02-22T21:55:42.487Z
Manu
<p>I'm developing a route planner, and I was reading some graph theory.</p>

<p>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).</p>

<p>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:</p>

<p><strong>Input:</strong></p>

<ul>
<li>Graph</li>
<li>List of initial nodes</li>
<li>List of end nodes</li>
</ul>

<p><strong>Output:</strong></p>

<ul>
<li>Node A</li>
<li>Node B</li>
<li>Shortest path</li>
</ul>

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

CC BY-SA 3.0
2013-02-22T22:41:17.297Z
This does not appear to be a *research-level* question in theoretical computer science to me.
David Eppstein
<graph-theory><graph-algorithms>
Algorithm to find shortest path from a set of nodes to another set of nodes?
jperelli
# Algorithm to find shortest path from a set of nodes to another set of nodes?

(Asked by: username_0 on 2013-02-22)

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.

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: This does not appear to be a *research-level* question in theoretical computer science to me.  

---

## 1 answers

### Answer by username_2 on 2013-02-22. Score: 11 | Accepted answer

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


---

