Найти цикл наименьшей длины в ориентированном графе с положительными весами - PullRequest
Новая
       3

Найти цикл наименьшей длины в ориентированном графе с положительными весами

16 голосов
/ 12 октября 2010

Мне задали этот вопрос в интервью, но я не смог придумать достойного решения. Итак, я сказал им наивный подход - найти все циклы, а затем выбрать цикл с наименьшей длиной.

Мне любопытно узнать, как эффективно решить эту проблему.

Ответы [ 6 ]

28 голосов
/ 12 октября 2010

Вы можете легко изменить Алгоритм Флойд-Варшалла . (Если вы совсем не знакомы с теорией графов, я предлагаю проверить ее, например, получить копию Введение в алгоритмы ).

Традиционно вы запускаете path[i][i] = 0 для каждого i. Но вместо этого вы можете начать с path[i][i] = INFINITY. Это не повлияет на сам алгоритм, так как эти нули в любом случае не использовались в вычислениях (поскольку путь path[i][j] никогда не изменится для k == i или k == j).

В конце, path[i][i] - это длина кратчайшего цикла, проходящего через i. Следовательно, вам нужно найти min(path[i][i]) для всех i. И если вам нужен сам цикл (не только его длина), вы можете сделать это так же, как это обычно делается с обычными путями: запоминая k во время выполнения алгоритма.

Кроме того, вы также можете использовать алгоритм Дейкстры , чтобы найти кратчайший цикл, проходящий через любой данный узел. Если вы запустите эту модифицированную Dijkstra для каждого узла, вы получите тот же результат, что и с Floyd-Warshall. А поскольку у каждого Дейкстры есть O(n^2), вы получите одинаковую O(n^3) общую сложность.

6 голосов
/ 02 ноября 2015

Псевдокод - это простая модификация алгоритма Дейкстры. 

for all u in V:
   for all v in V:
      path[u][v] = infinity

for all s in V:
   path[s][s] = 0
   H = makequeue (V) .. using pathvalues in path[s] array as keys
   while H is not empty:
      u = deletemin(H)
      for all edges (u,v) in E:
         if path[s][v] > path[s][u] + l(u, v) or path[s][s] == 0:
            path[s][v] = path[s][u] + l(u,v)
         decreaseKey(H, v)

lengthMinCycle = INT_MAX

for all v in V:
   if path[v][v] < lengthMinCycle & path[v][v] != 0 :
      lengthMinCycle = path[v][v]

if lengthMinCycle == INT_MAX:
   print(“The graph is acyclic.”)

else:
   print(“Length of minimum cycle is ”, lengthMinCycle)

Сложность времени: O (| V | ^ 3)

0 голосов
/ 10 августа 2018

Ниже приведена простая модификация алгоритма Флойда - Warshell. 

V = 4
INF = 999999</p>

<p>def minimumCycleLength(graph): 
    dist =  [[0]*V for i in range(V)]
    for i in range(V):
            for j in range(V):
                dist[i][j] = graph[i][j];
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j] ,dist[i][k]+ dist[k][j])
    length = INF
    for i in range(V):
        for j in range(V):
            length = min(length,dist[i][j]) 
    return length</p>

<code>graph = [ [INF, 1, 1,INF],
        [INF, INF, 1,INF],
        [1, INF, INF, 1],
        [INF, INF, INF, 1] ]
length = minimumCycleLength(graph)
print length
</code>
0 голосов
/ 01 ноября 2016

Мы также можем использовать алгоритм ветвления и привязки для задачи коммивояжера, так как ваш вопрос совпадает с TSP. http://lcm.csa.iisc.ernet.in/dsa/node187.html

0 голосов
/ 12 октября 2010

Что вам нужно будет сделать, это назначить другой вес каждому узлу, который всегда равен 1. Теперь запустите любой алгоритм кратчайшего пути от одного узла к тому же узлу, используя эти веса. Но, рассматривая промежуточные пути, вы должны будете игнорировать пути, фактические веса которых отрицательны.

0 голосов
/ 12 октября 2010
  • Выполнить DFS
  • Во время DFS следите за типом края
  • Тип ребер Tree Edge, Back Edge, Down Edge и Parent Edge
  • Отслеживайте, когда вы получаете Back Edge и у вас есть другой счетчик для получения длины.

Подробнее см. Algorithms in C++ Part5 - Robert Sedgwick

...