# Minimal lexicographical path on DAG in O(||V| + |E|)

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)$$.

• What is the definition of a lexicographical path? Oct 4, 2021 at 12:13