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

Question

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

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

Answer 1

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

Традиционно вы начинаете 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) общая сложность.

Answer 2

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

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)

Answer 3

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

Answer 4

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

Answer 5

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

Увидеть Algorithms in C++ Part5 - Robert Sedgwick Больше подробностей

Answer 6

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

 V = 4
INF = 999999
defimumCycleLength(graph): 
    dist =  [[0]*V для i в диапазоне (V)]
    для я в диапазоне (V):
            для j в диапазоне (V):
                dist[i][j] = graph[i][j];
    для k в диапазоне (V):
        для я в диапазоне (V):
            для j в диапазоне (V):
                dist[i][j] = min(dist[i][j],dist[i][k]+ dist[k][j])
    длина = INF
    для я в диапазоне (V):
        для j в диапазоне (V):
            длина = min (длина,dist[i][j]) 
    возвращаемая длина
graph = [ [INF, 1, 1,INF],
        [INF, INF, 1,INF],
        [1, INF, INF, 1],
        [INF, INF, INF, 1] ]
length = minimumCycleLength(graph)
print length