DIETED Acyclic 그래프 N 단계 내에서 최단 경로

Question

긍정적으로 가중 된 Directed Acyclic Graph에서 최단 경로를 찾는 문제가 있지만 N 단계의 최대 수 (경로의 가장자리)의 제한이 있습니다. 경로가 있다고 가정합니다. 그래프의 추가 속성은 에지 (i, j)가 그래프에 있으면 모든 에지 (i, k)도 i < k <j에 대한 그래프에 있음을 의미합니다. 나는 그래프의 시작과 끝 사이의 최단 경로 (토폴로지 정렬 후)에만 관심이있다.

나는 O (V + E)의 Directed Acyclic Graph에서 최단 경로에 대한 효율적인 알고리즘이 있지만 단계 제한을 고려하지 않음을 알고 있습니다. O ((V + E) * N)를 만드는 방법은 생각할 수 없지만 1000 노드와 100 단계의 그래프를 처리 할 수있을만큼 좋기 때문에 이상적인 성능이 될 것입니다.

예를 들어 다음을 고려하십시오. graph.

문제는 최대 k = 3 단계 (에지)를 사용하여 최단 경로를 찾는 것입니다. 답은 6 (경로 1-> 4-> 5-> 6)입니다.

Answer 1

실제로는 O(N + M)입니다. 여기서 N은 정점의 수이고, M은 모서리의 수입니다. http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

경로를 (내가 geeksforgeeks의 코드를 사용하고 있습니다) 찾기 : 대신 int dist[V] 사용 pair<int, int> dist[V] 여기에서 자세한 정보를 찾을 수 있습니다. 처음에는 dist[S] = {0, -1}입니다. 따라서이 상태에서 if (dist[i->getV()].first > dist[u].first + i->getWeight())을 부모로 설정하려면 dist[i->getV()] = {dist[u].first + i->getWeight(), u}으로 설정해야합니다. ,

void restore(int v) { 
    if(dist[v].second == -1) return; 
    else answer.push_back(v); 
    if(v == START_POINT) return; 
    restore(dist[v].second); 
} 

이 문제는 (경로에 사용되는 에지) N 단계 내에서 최단 경로를 얻는 것입니다 restore(FINAL_POINT)