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

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

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

Источник

2 ответа

Решение

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

Вот как:

  • Делаем топологическое упорядочение v1 > v2 >... > vn..
  • Выберите любую вершину vj...
  • Пусть расст (vj) быть самым длинным расстоянием от v1 в vj, Тогда расст (vj) = Макс (расстояние (u1) + 1, расстояние (u2) +1,..., р-н (uk) +1) где u1,u2,...,uk являются предшественниками vj,
  • path(vj)=path(ui)U{vj} где ui предшественник с максимальной длиной (то есть тот, который мы выбрали в dist (vj)).
  • Рассчитайте это для каждого vj,
  • Самый длинный путь - это максимум dist(vj) с фактическим путем path(vj),
Источник

Я предполагаю, что следующий алгоритм может работать, чтобы найти самый длинный путь, используя поиск в глубину. Вопрос между ** - это изменения в алгоритме 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

Источник
Другие вопросы по тегам