Самый длинный простой путь в разреженных циклических графах

Дано: невзвешенный направленный граф (G=(E,V)), который может содержать любое количество циклов.

Цель: для всех вершин мне нужен самый длинный простой путь к некоторой целевой вершине X в V.

Идея алгоритма:

For each v in V
  v.distanceToTarget = DepthFirstSearch(v)
Next

DepthFirstSearch(v as Vertex)
  if v = target then
    'Distance towards target is 0 for target itself
    return 0
  elseif v.isVisitedInCurrentDFSPath then
    'Cycle found -> I wont find the target when I go around in cycles -> abort
    return -infinity
  else
    'Return the maximum Distance of all Successors + 1
    return max(v.Successors.ForEach(Function(v) DepthFirstSearch(v) )) + 1
  end if

Это верно для всех случаев? (Предполагая, что цель может быть достигнута из каждой вершины)

Количество ребер в моих графах очень мало. Предположим |Е| ‹= 3*|В| держит. Как мне вычислить среднюю временную сложность?

Спасибо!


graph algorithm longest-path depth-first-search
person Xardestro    schedule 22.10.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Временная сложность — это то, какие значения больше всего влияют на время выполнения. В вашем случае вы оцениваете все возможные пути между v и target. Это в основном O (количество маршрутов). Теперь вам нужно выяснить, как выразить количество всех возможных маршрутов через E и V.

Скорее всего, результатом будет что-то вроде O (exp (E)) или O (exp (V)), потому что количество маршрутов, проходящих через каждый узел / вершину, увеличивается экспоненциально, когда вы добавляете новые возможные маршруты.

РЕДАКТИРОВАТЬ: я пропустил деталь, которую вы просили о средней временной сложности, которая означала бы амортизированную сложность. Но поскольку ваш алгоритм всегда оценивает все возможные маршруты, сложность в худшем случае такая же, как и средняя сложность.

person Pauli Nieminen    schedule 22.10.2016