I'm not sure of the name of this problem so haven't really been able to research it. I have a complete weighted graph with a start and end node and n distinct sets of nodes (lets call them red, blue and green), each with m member nodes.

I need to find the shortest path from start to end and must pass through exactly one red, one blue and one green node; is there an algorithm for this?

An extension would be that I need to find the shortest path while visiting blue first, then green, then red (again, exactly once each); is there one for this?

  • $\begingroup$ If the order of visits (green first, blue later, etc.) is given, then this can be done by making as many copies of the graph as these sets, each "layer" corresponding to one set. With unknown order you can do the same using $2^k$ layers/copies corresponding to any combination of visited/unvisited. As for whether you can do it faster, I don't know off the top of my head. $\endgroup$ – dtldarek Oct 6 '16 at 17:06

If your graph $G=(V,E)$ isn't too big, you can achieve this rather easily with linear programming: use binary variables $x_{ij}$ that take value $1$ if and only if edge $(i,j)\in E$ of length $c_{ij}\ge 0$ belongs to the path. You want to minimize the length of the path: $$ \sum_{(i,j)\in E}c_{ij}x_{ij} $$ subject to:

  1. Flow conservation constraints: $$ \sum_{(i,j)\in E}x_{ij} = \sum_{(j,i)\in E}x_{ij} \quad \forall i\in V $$
  2. Send one unit of flow from source node $s$: $$ \sum_{(s,j)\in E}x_{sj} = 1 $$
  3. Send one unit of flow to target node $t$: $$ \sum_{(j,t)\in E}x_{jt} = 1 $$
  4. Pass through exactly one red node among $V_{red}\subset V$, one green node among $V_{green}\subset V$ and one blue node among $V_{blue}\subset V$: define binary variables $y_i$ that take value $1$ if and only if node $i\in V$ is visited and impose $$ \sum_{i\in V_{red}}y_i = \sum_{i\in V_{blue}}y_i=\sum_{i\in V_{green}}y_i=1\\ y_i \le \sum_{j \in V}x_{ij}\quad \forall i \in V $$

If the visiting order (blue-green-red) is also imposed, it is a little tricker, you need extra variables $u_i\in[1,n] $ - they represent the rank of node $i$ in the shortest path - and add the following constraints:

  1. The source $s$ has rank $1$: $$ u_{s}=1 $$
  2. If edge $(i,j)$ belongs to the path, then $u_i\le u_j+1$: $$ u_i\le u_j+1+M(1-x_{ij}) \quad \forall (i,j)\in E $$
  3. Blue before green: $$ u_i \le u_j+1 +M(2-y_i-y_j)\quad \forall i,j\in V_{blue}\times V_{green} $$
  4. Green before red: $$ u_i \le u_j+1 +M(2-y_i-y_j)\quad \forall i,j\in V_{green}\times V_{red} $$

A trivial way of doing this is by iteration though all triples $(x_1,x_2,x_3)$, where $x_1$ is a red, $x_2$ a blue and $x_3$ a green node. For each iteration, remove all other coloured nodes out of the graph. Then iterate through all permutations $\pi$ of size 3, and find a shortest path between the start node and $x_{\pi(1)}$, between $x_{\pi(1)}$ and $x_{\pi(2)}$, between $x_{\pi(2)}$ and $x_{\pi(3)}$ and between $x_{\pi(3)}$ and the target node, by using a standard algorithm for shortest paths. Then, add the shortest paths together and sum the weights of the edges.

By using this way, you iterate through many possible paths. Find the minimum of all, that's the shortest path that you want to have.

Of course, this algorithm isn't efficient at all. But I doubt that you can find an algorithm in polynomial time. It could be possible that this is equivalent to the traveling salesman problem, though I'm not sure.


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.