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, 2021 at 12:13

0

Reset to default

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.