Как найти самый длинный простой путь (включая все промежуточные узлы) в ориентированном циклическом графе?

Я искал здесь, как найти самый длинный простой путь в ориентированном циклическом графе (это означает, что каждый узел посещается только один раз, чтобы избежать бесконечности пути), и наткнулся на такие решения, как this. Однако все такие решения, которые я нашел, показывают только то, как вычислить длину самого длинного пути, а не фактические узлы, участвующие в этом пути.

Поэтому у меня вопрос: как можно изменить такой алгоритм, как который, чтобы он извлекал узлы, участвующие в самом длинном пути? Подобно тому, как алгоритм кратчайшего пути для всех пар Флойда-Варшалла может быть изменен чтобы разрешить реконструкцию пути.


algorithm longest-path graph-algorithm
person LogicChains    schedule 14.11.2014    source источник
comment
Принятый ответ в вопросе, на который вы ссылаетесь, можно тривиально изменить, чтобы записать путь, а также его длину.   -  person j_random_hacker    schedule 14.11.2014
comment
@j_random_hacker как? Может быть, для вас это тривиально, но для меня это не так, поэтому я задал этот вопрос.   -  person LogicChains    schedule 15.11.2014
comment
Когда path изменится? Когда это произойдет, обновите также список узлов на пути. Когда bestPath изменится? Перепишите это как выражение if: теперь в теле этого оператора if вы можете обновить список узлов в лучшем на данный момент пути одновременно с обновлением его длины.   -  person j_random_hacker    schedule 15.11.2014

Ответы (2)


arrow_upward
3
arrow_downward

Чтобы найти реальный путь, все, что вам нужно, - это отслеживать путь наибольшего расстояния (вы получили этот путь от предшественников). The longest path of vj= the longest path among precedessors U {vj}

Вот как:

  • Сделайте топологический заказ v1 > v2 >... > vn ..
  • Выберите любую вершину _3 _...
  • Пусть dist (vj) будет самым длинным расстоянием от v1 до vj. Тогда dist (_7 _) = max (dist (_8 _) + 1, dist (_9 _) + 1, ..., dist (_10 _) + 1), где u1,u2,...,uk - предшественники vj.
  • path(vj)=path(ui)U{vj}, где ui - предшественник с максимальной длиной (то есть тот, который мы выбрали в dist (vj)).
  • Вычислите это для каждого vj.
  • Самый длинный путь - это максимум dist(vj) при фактическом пути path(vj).
person Xline    schedule 15.11.2014

arrow_upward
0
arrow_downward

Я предполагаю, что следующий алгоритм может работать, чтобы найти самый длинный путь с использованием поиска в глубину. Между ** - это изменения в алгоритме DFS.

DFS(G)
  For each u  V[G]
   {done(u)=0;
    Pre(u)=NULL;}
  Time=0;  
  For each uV[G]
   If done(u) == 0
   {**longest(u)=0**;
    DFS_VISIT(u);}

DFS_VISIT(u)
Done(u)=-1;
Discover(u)=time++;
For each v adjacent to u
If done(v)==0
    { pre(v)=u;
      **Longest(v)=longest(u)+1**;
      DFS_VISIT(v);}
Done(u)=1;
Finish(u)=time++`

Найдя все самое длинное (v), я могу найти самое большое значение и сделать вывод, что это самый длинный путь. Как ты думаешь @Xline

person StevieG    schedule 20.03.2016