Найти цикл наименьшей длины в ориентированном графе с положительными весами

Мне задали этот вопрос в интервью, но я не смог придумать достойного решения. Итак, я рассказал им о наивном подходе: найти все циклы и выбрать цикл с наименьшей длиной.

Мне любопытно узнать, как эффективно решить эту проблему.