Исправленный ациклический график кратчайшего пути в пределах N шагов

Question

У меня проблема с поиском кратчайшего пути в положительно взвешенном ациклическом графике с прямым взвешиванием, но с ограничением максимального числа N шагов (ребра на пути). Предполагается, что путь существует. Дополнительным свойством графа является то, что если ребро (i, j) находится в графе, то любое ребро (i, k) также находится в графике для i < k < j. Меня интересует только кратчайший путь между началом и концом графика (после топологической сортировки).

Я знаю, что существует эффективный алгоритм для кратчайшего пути в Directed Acyclic Graph в O (V + E), но он не учитывает предел шагов. Я не могу придумать, как сделать 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); 
} 

Вызова его с restore(FINAL_POINT)