Вопрос по algorithm, shortest-path, graph, data-structures – график - Как найти минимальный направленный цикл (минимальный общий вес)?
======================================================================================================================================

Вот акциз:

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?

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

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

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

1. So ur algo is incomplete
2. 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))

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



Ты можешь использовать[Флойд-Воршалл](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:**

```
run Floyd Warshall on the graph
min <- infinity
vertex <- None
for each pair of vertices u,v
    if (dist(u,v) + dist(v,u) < min):
           min <- dist(u,v) + dist(v,u)
           pair <- (u,v)
return path(u,v) + path(v,u)

```

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

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

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



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

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



> 
> Is my algorithm correct?
> 
> 
> 

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

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