0
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ What is the definition of a lexicographical path? $\endgroup$
    – Gamow
    Oct 4 '21 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.