график - Как найти минимальный направленный цикл (минимальный общий вес)?
=========================================================================

Вот акциз:

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? 

Ты можешь использовать[Флойд-Воршалл](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) Алгоритм здесь.

Алгоритм Флойда-Варшалла находит кратчайший путь между**all pairs** вершин.

Алгоритм тогда очень прост, пройдитесь по всем парам`(u,v)`, а также**find the pair that minimized `dist(u,v)+dist(v,u)`**, поскольку эта пара указывает на цикл из`u` в`u` с весом`dist(u,v)+dist(v,u)`, Если график также допускает самоциклы (ребро`(u,u)`), вам также необходимо проверить их в одиночку, потому что эти циклы (и только они) не были проверены алгоритмом.

**pseudo code:**

`path(u,v) + path(v,u)` на самом деле путь, найденный из u в v, а затем из v в u, что является циклом.

Время выполнения алгоритма`O(n^3)`, так как Флойд-Уоршалл является горлышком бутылки, так как цикл принимает`O(n^2)` время.

Я думаю, что правильность здесь тривиальна, но дайте мне знать, если вы не согласны со мной, и я постараюсь объяснить это лучше.



«Для каждой вершины она может указывать на одного из своих предков и, таким образом, формировать цикл».

Я думаю, что это может указывать на любого из его предков, что означает N

Кроме того, как вы собираетесь отмечать вершины, когда вы вышли из его dfs, вы можете прийти туда снова из другой вершины, и это будет другой цикл. Так что это не (N + M) DFS больше.

So ur algo is incomplete
same here

3.
During one dfs, I think the vertex should be either unseen, or check, and for checked u can store the minimum weight for the path to the starting vertex. So if on some other stage u find an edge to that vertex u don't have to search for this path any more.
This dfs will find the minimum directed cycle containing first vertex. and it's O(n^2) (O(n+m) if u store the graph as list)

Так что, если сделать это из любой другой вершины, это будет O (n ^ 3) (O (n * (n + m))

Извините за мой английский и я не очень хорош в терминологии



Is my algorithm correct?

Позвольте мне привести встречный пример. Представьте, что вы запускаете DFS из`u`Есть два пути`p1` а также`p2` от`u` в`v` и 1 путь`p3` от`v` вернуться к`u`, `p1` короче чем`p2`.

Предположим, вы начинаете с`p2` путь к`v`и вернитесь к`u` по пути`p3`, Один цикл найден, но, по-видимому, он не минимален. Тогда вы продолжаете исследовать`u` взяв`p1` путь, но так как`v` полностью исследуется, DFS заканчивается без нахождения минимального цикла.



Я делал подобные вещи, но я не использовал ни один посещенный массив для dfs (который был необходим для правильной работы моего алгоритма), и поэтому я понял, что мой алгоритм имеет экспоненциальную сложность.

Поскольку вы находите все циклы, невозможно найти все циклы менее чем за экспоненциальное время, поскольку может быть 2 ^ (e-v + 1) циклов.