Кратчайший путь прямого ациклического графа за N шагов

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

Я знаю, что существует эффективный алгоритм кратчайшего пути в направленном ациклическом графе в O (V + E), но он не учитывает ограничение количества шагов. Я не могу придумать, как сделать это O ((V + E) * N), но это была бы идеальная производительность, поскольку она должна быть достаточно хорошей для обработки графиков из 1000 узлов и 100 шагов.

Например, рассмотрим следующий график.

Задача состоит в том, чтобы найти кратчайший путь, используя не более k = 3 шагов (ребер). Ответ - 6 (путь 1-> 4-> 5-> 6).


graph directed-acyclic-graphs algorithm shortest-path
person kuba1024g    schedule 05.02.2017    source источник
comment
@SaeedAmiri Проблема в том, чтобы получить кратчайший путь в пределах N шагов (ребра, используемые для пути), а не просто кратчайший путь ...   -  person kuba1024g    schedule 05.02.2017
comment
Как написано, задача требует пути длиной не более N, а позже обещается, что такой путь существует, если такой путь существует, то, безусловно, кратчайший путь имеет длину не более N.   -  person Saeed Amiri    schedule 06.02.2017
comment
@SaeedAmiri четко указано, что график взвешен   -  person kuba1024g    schedule 06.02.2017
comment
Кажется, я неправильно это понял.   -  person Saeed Amiri    schedule 06.02.2017
comment
Добавлю пример   -  person kuba1024g    schedule 06.02.2017

Ответы (1)


arrow_upward
0
arrow_downward

Фактически это 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()) вам нужно установить parent как 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)

person Rasul Kerimov    schedule 05.02.2017
comment
Мне очень жаль, но в этом ответе отсутствует суть. Проблема состоит в том, чтобы получить кратчайший путь в пределах N шагов (ребра, используемые для пути), а не просто кратчайший путь. - person kuba1024g; 05.02.2017
comment
@ kuba1024g Вам нужно сохранить родительский элемент для каждой вершины. Затем рекурсивно восстановите свой путь. - person Rasul Kerimov; 06.02.2017