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

Вот акциз:

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?
 Keeblebrox05 мая 2012 г., 00:36
Не ясно, с чем вы обращаетесь за помощью. Вы просите о помощи, чтобы определить сложность вашего времени?
 n.m.05 мая 2012 г., 01:17
Ваш алгоритм неполон. Что вы будете делать, если встретите вершину, которую уже видели?
 Jackson Tale05 мая 2012 г., 00:47
Хорошо я редактировал мой вопрос
 Saeed Amiri05 мая 2012 г., 02:33
3в1 вопрос :)

Ответы на вопрос(4)

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

Я думаю, что это может указывать на любого из его предков, что означает 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))

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

Решение Вопроса

Ты можешь использоватьФлойд-Воршалл Алгоритм здесь.

Алгоритм Флойда-Варшалла находит кратчайший путь между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) время.

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

 Jackson Tale05 мая 2012 г., 09:45
Очень ясно, спасибо действительно @amit
 30 мар. 2013 г., 07:03
Что не так с dist (u, u)? Если это не дает длину кратчайшего цикла u & # x2192; ... & # x2192; u (включая циклы self), речь идет о разныхFloyd-Marshals?
 Jackson Tale05 мая 2012 г., 09:14
Благодарю. Я полагаю, что ваше предложение верно, хотя я все еще пытаюсь понять это. Я понимаю алгоритм Флойда, и он обязательно находит все пары кратчайшего пути. Таким образом, в итоге мы получаем матрицу с кратчайшим весом между всеми парами. И затем, чтобы выяснить, какой цикл имеет минимальные суммарные веса, мы просто можем снова выполнить матрицу. Если matrix [i] [j]! = MAX_INT и matrix [i] [j]! = MAX_INT, то i и j имеют цикл, а итог = matrix [i] [j] + matrix [j] [i], тогда мы можем найти минимальный, я прав? Чтобы записать структуру цикла, мы должны использовать другую родительскую матрицу, верно?
 05 мая 2012 г., 09:19
@JacksonTale: (1) Вы правы, также обратите внимание на мое редактирование: это решение не заботится о собственных циклах (ребра, как(u,u)), поэтому, если они разрешены на графике - это нужно будет проверить дополнительно (это легко). Обратите внимание, что как только вы нашли, какая пара является обязательной, вы можете использовать dijkstra или BF изu найти путьu->...->vи затем снова изv найтиv->...->uбез изменения общей сложности алгоритма, поэтому получение фактического пути не является проблемой для этой проблемы.

Is my algorithm correct?

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

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

 03 нояб. 2012 г., 12:59
Спасибо за совет. Обновлено.
 21 окт. 2012 г., 20:52
Для большей читабельности вы должны использовать формат кода, заключая в себе имена переменных с помощью обратных галочек, таких как `this`

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

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

Ваш ответ на вопрос