# Shortest path given correct order of colours?

I have a directed graph $$G=(V,E)$$ where each vertex is a 4-D coordinate $$v: (x, y, z, c)$$ representing spatial coordinates $$x, y, z \in \mathbb{R}$$ and the non-physical parameter colour $$c \in (c_{1}, c_{2},... c_{n})$$. The edge weights $$\omega_{v_{a} \to v_{b}}: f(x, y, z)$$ are purely a function of three of the four dimensions, as this is a physical problem.

Trouble is, I wish to find the shortest path given a specific sequence of colors (eg. $$c_{2}, c_{5}, c_{1}, c_{1}, c_{3}, c_{4}$$). It's difficult to incorporate this into the weight function as it is non-physical. Are there well-established path traversal algorithms that find the shortest path through coloured vertices, given the starting vertex, ending vertex, and the sequence it needs to pass through? I wonder if there is already a family of algorithms that describe this problem?

I've considered something like a Hidden Markov Model that abstracts vertices of colours into hidden states, but I am not sure how to prevent one state from being visited again (whereas in a directed acyclic graph I can prevent revisiting the same vertex).

• This sounds like it's minimaxable. May 3, 2021 at 15:42

Use a product construction, to construct a new graph whose vertices are given $$(x,y,z,k)$$, where $$k$$ counts the index into the sequence of colors (i.e., we are currently at $$k$$th vertex in that sequence). Then, find the shortest path in this new graph using any standard shortest-path algorithm. If all weights are non-negative, you can use Dijkstra's algorithm on this graph; otherwise you can use Bellman-Ford on this graph.

See How hard is finding the shortest path in a graph matching a given regular language?. Your problem is a special case of the problem solved there. (Possibly also useful: Product construction for given two finite automata .)

Specifically, here is how the product construction works in your setting. Let $$(c_1,c_2,\dots,c_q)$$ be the desired sequence of colors. Then, for each $$k=1,2,\dots,q-1$$, you'll have an edge $$(x,y,z,k) \to (x,y,z,k+1)$$ in the new graph if there is an edge $$(x,y,z,c_k) \to (x,y,z,c_{k+1})$$ in the original graph; the weight of the edge is copied over from the corresponding edge in the original graph. Now, find the shortest path from $$(x_0,y_0,z_0,1)$$ to $$(x_1,y_1,z_1,q)$$ in the new graph, where $$(x_0,y_0,z_0,c_1)$$ is the starting vertex in the original graph and $$(x_1,y_1,z_1,c_q)$$ is the ending vertex in the original graph.

• Thank you for this reference! I'm completely new to theory of computing - some of the language in those links are inaccessible to me. My confusion is - say in the image drawn above - there are multiple yellow spots (4) but they should be chosen at t = 2, 4, 5. What is a strategy to make this into the 4th dimension $k$? May 3, 2021 at 5:31
• @batlike, I edited my answer to explain. See the last paragraph.
– D.W.
May 3, 2021 at 5:56
• This is a very interesting approach. I wonder if there is also a way to make this a probabilistic search as well, where some colours in the expected sequence can be "skipped". Thank you for this proposal! May 4, 2021 at 15:42
• @batlike, I'd guess yes, but I'm not sure what is meant by probabilistic, so I'm not sure. If you can express the constraints on the sequence of colors as a deterministic finite automaton, you can generalize this approach to handle that as well.
– D.W.
May 4, 2021 at 17:58