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

Question

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.

Answer 1

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.