Summary: Given an alphabet \(\Sigma\), a (directed) graph \(G\) whose edges are weighted and \(\Sigma\)-labeled, and a formal language \(L\subseteq\Sigma^*\), the formal-language-constrained shortest/simple path problem consists of finding a shortest (simple) path \(p\) in \(G\) complying with the additional constraint that \(l(p) \in L\). Here \(l(p)\) denotes the unique word obtained by concatenating the \(\Sigma\)-labels of the edges along the path \(p\). The main contributions of this paper include the following: We show that the formal-language-constrained shortest path problem is solvable efficiently in polynomial time when \(L\) is restricted to be a Context-Free Language (CFL). When \(L\) is specified as a regular language we provide algorithms with improved space and time bounds. In contrast, we show that the problem of finding a simple path between a source and a given destination is NP-hard, even when \(L\) is restricted to fixed simple regular languages and to very simple classes of graphs (e.g., complete grids). For the class of treewidth-bounded graphs, we show that (i) the problem of finding a regular-language-constrained simple path between source and destination is solvable in polynomial time and (ii) the extension to finding CFL-constrained simple paths is NP-complete. Our results extend the previous results in \textit{A. O. Mendelzon} and \textit{P. T. Wood} [SIAM J. Comput. 24, 1235-1258 (1995; Zbl 0845.68033)], \textit{K. Scott, G. Pabon-Jimenez} and \textit{D. Bernstein} [(*) Proceedings of the 76th Annual Meeting of the Transportation Research Board (1997)] and \textit{M. Yannakakis} [Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Database Systems, 230-242 (1990)]. Several additional extensions and applications of our results in the context of transportation problems are presented. For instance, as a corollary of our results, we obtain a polynomial-time algorithm for the best \(k\)-similar path problem studied in (*). The previous best algorithm was given in (*) and takes exponential time in the worst case.