2
$\begingroup$

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.

enter image description here

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

$\endgroup$
1
  • $\begingroup$ This sounds like it's minimaxable. $\endgroup$
    – Flater
    May 3 at 15:42
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$
    – batlike
    May 3 at 5:31
  • $\begingroup$ @batlike, I edited my answer to explain. See the last paragraph. $\endgroup$
    – D.W.
    May 3 at 5:56
  • $\begingroup$ 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! $\endgroup$
    – batlike
    May 4 at 15:42
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    May 4 at 17:58

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.