Let's assume, that we have directed asyclic graph and nodes U and V. Every edge of this graph is marked with alphabet letter (alphabet size is fixed). Is there any way to answer, what is the shortest lexicographical path from U to V in $O(|V| + |E|)$ time? The fastest I can get is $O(|V| + |E|^2)$.
-
1$\begingroup$ What is the definition of a lexicographical path? $\endgroup$– GamowOct 4, 2021 at 12:13