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

6

Вот акциз:

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?
Хорошо я редактировал мой вопрос Jackson Tale
Ваш алгоритм неполон. Что вы будете делать, если встретите вершину, которую уже видели? n.m.
3в1 вопрос :) Saeed Amiri
Не ясно, с чем вы обращаетесь за помощью. Вы просите о помощи, чтобы определить сложность вашего времени? Keeblebrox

Ваш Ответ

4   ответа
2

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

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

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

19

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

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

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

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

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

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

2

Is my algorithm correct?

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

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

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

Похожие вопросы