Formal-language-constrained path problems
Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal language L ⊆ Σ*, the formal-language-constrained shortest/simple path problem consists of finding a shortest (simple) path p in G complying with the additional …