희박한 순환 그래프에서 가장 긴 단순 경로

Question

주어진 : 순환 수를 포함 할 수있는 비가 중 방향 그래프 (G = (E, 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 

이 모든 경우에 대한 정확 : 모든 정점 위해 나는 V에서 어떤 대상 정점 X에 가장 긴 간단한 경로

알고리즘의 아이디어를 원한다? (목표에 모든 정점에서 도달 할 수 있다고 가정)

그래프의 가장자리 수가 매우 적습니다. | E | < = 3 * | V | 보유. 평균 시간 복잡도는 어떻게 계산합니까?

감사합니다.

Answer 1

시간 복잡도는 런타임에 가장 큰 영향을주는 값입니다. 귀하의 경우에 v와 목표 사이의 모든 가능한 경로를 평가하십시오. 기본적으로 O (경로 수)입니다. 이제 가능한 모든 경로의 수를 E 및 V로 표현하는 방법을 알아야합니다.

O (exp (E)) 또는 O (exp (V))와 같은 결과는 가능한 모든 경로를 추가하면 각 노드/정점을 통과하는 경로가 기하 급수적으로 변합니다.

편집 : 평균 시간 복잡성에 대해 묻는 세부 정보가 없으므로 상각 된 복잡성이 발생합니다. 그러나 알고리즘이 항상 가능한 모든 경로를 평가할 때 최악의 복잡도는 평균 복잡도와 같습니다.