Вот акциз:

Let G be a weighted directed graph with n vertices and m edges, where all edges have positive weight. A directed cycle is a directed path that starts and ends at the same vertex and contains at least one edge. Give an O(n^3) algorithm to find a directed cycle in G of minimum total weight. Partial credit will be given for an O((n^2)*m) algorithm.

Вот мой алгоритм.

Я делаюDFS, Каждый раз, когда я нахожуback edgeЯ знаю, что у меня есть направленный цикл.

Тогда я временно пойду назад поparent array (пока я не проеду все вершины цикла) и вычислюtotal weights.

Тогда я сравниваюtotal weight этого цикла сmin. min всегда принимает минимальный общий вес. После завершения DFS наш минимальный направленный цикл также найден.

Хорошо, тогда о сложности времени.

Честно говоря, я не знаю временной сложности моего алгоритма.

Для DFS обход занимает O (m + n) (если m - количество ребер, а n - количество вершин). Для каждой вершины она может указывать на одного из своих предков и, таким образом, формировать цикл. Когда цикл найден, для суммирования общих весов требуется O (n).

Поэтому я думаю, что общее время составляет O (m + n * n). Но очевидно, что это неправильно, поскольку, как указано в акцизе, оптимальное время составляет O (n ^ 3), а нормальное время равно O (m * n ^ 2).

Может ли кто-нибудь помочь мне с:

Is my algorithm correct? What is the time complexity if my algorithm is correct? Is there any better algorithm for this problem?