How hard is finding the shortest path in a graph matching a given regular language?

Suppose we are given a directed graph $$G = (V, E)$$ with edge weights $$w : E \rightarrow \mathbb{R}$$ (we can assume there are no negative cycles) and edge labels $$\ell : E \rightarrow \Sigma$$ from some alphabet $$\Sigma$$. We are also given a description of an NFA $$M$$ (or DFA, or regular expression) accepting some regular language $$L(M) \subseteq \Sigma^*$$, and two vertices $$s, t \in V$$.

The problem is to find the shortest path in $$G$$ from $$s$$ to $$t$$ whose edge labels form a string that is a member of $$L(M)$$. That is, we only consider paths $$e_1, e_2, \dots, e_k$$ where $$\ell(e_1) \ell(e_2) \dots \ell(e_k) \in L(M)$$.

Can this problem be solved in time polynomial in $$|V|$$, $$|E|$$, and $$|M|$$?

This question was inspired by these other questions about special cases of this problem.

• Nice. Related is the concept of "Multi-State Mazes", where the direction in which you are allowed to exit a spot depends on the way you entered it. Commented Dec 29, 2019 at 1:25
• @HendrikJan Yep, and those can of course be solved by the same sort of product construction. When in doubt, just spam more vertices! Commented Dec 30, 2019 at 0:43
• In this question and its answer, the same vertex can be visited multiple times in a path and in "the shortest path", unlike the common definition of "path", where repeated vertices are not allowed in a path. Commented Jan 7, 2022 at 20:38

This problem can be solved in polynomial time by a product construction. Construct the graph $$G^\prime$$ as follows:

• The vertices of $$G^\prime$$ are $$(V \times M) \cup \{\#\}$$, i.e. all pairs of a vertex of $$G$$ and a state of $$M$$, together with an extra vertex identified by the arbitrary symbol $$\#$$.
• For each edge in $$e \in E$$ from $$v_1$$ to $$v_2$$, add an edge in $$G^\prime$$ from $$(v_1, m_1)$$ to $$(v_2, m_2)$$ with weight $$w(e)$$ if and only if there is an edge in $$M$$ from $$m_1$$ to $$m_2$$ that is labeled $$\ell(e)$$.
• For each accepting state $$m$$ in $$M$$, add an edge in $$G^\prime$$ from $$(t, m)$$ to $$\#$$ with weight 0.

Then the shortest path in $$G^\prime$$ from $$(s, m_0)$$ to $$\#$$ (where $$m_0$$ is the initial state of $$M$$) gives the shortest path in $$G$$ from $$s$$ to $$t$$ matching $$L(M)$$. There cannot be a negative cycle in $$G^\prime$$, since dropping the $$m$$ states from the vertex labels would give a negative cycle in $$G$$, which we are assuming does not exist.

This also answers the question if $$M$$ is a DFA or regular expression instead of an NFA, since these can be converted to an equivalent NFA in polynomial time. We can also directly handle NFAs with $$\varepsilon$$-transitions: if $$M$$ contains an $$\varepsilon$$-transition from $$m_1$$ to $$m_2$$, add an edge in $$G^\prime$$ with weight 0 from $$(v, m_1)$$ to $$(v, m_2)$$ for each $$v \in V$$.

For fixed $$M$$, the product graph $$G^\prime$$ has only linearly more vertices and edges than the original graph $$G$$. This means that any fixed problem of the form "find the shortest path that visits edges in such-and-such order", such as the problems linked in the question, can be solved just as fast as the ordinary shortest path problem asymptotically.

As an implementation detail, note that there is no need to actually write down the whole product graph in memory. The vertices and edges can be generated dynamically while running the shortest path algorithm, which allows unused vertices to be skipped entirely.