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

Question

Дано: Невзвешенный направленный график (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 

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

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

Спасибо!

Answer 1

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

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

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