Самый длинный путь для взвешенного ориентированного ациклического графа

Question

Я пытаюсь осмыслить эту проблему, а затем написать для нее код Java. Я знаю, что здесь было какое-то обсуждение, но я не вижу много ответчиков, поэтому я хотел бы повторить вопрос, записав свои мысли, и я надеюсь получить некоторую обратную связь от вас, ребята. Спасибо!

Мои мысли: для каждого конечного узла найти самый длинный путь от корневого узла к нему для всех путей найти максимальную длину пути

Однако разве это не просто грубая сила? Есть ли более элегантные решения для этого?

Я слышал об использовании алгоритма Джикстры с отрицательными весами, но в некоторых местах говорится, что это работает только в определенных случаях? Я также видел предложения по алгоритму Беллмана Форда, но разве он не используется для поиска кратчайшего пути?

Спасибо!!

Answer 1

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

// To hold an edge list for every path. 
YList allShortestPaths = new YList();

// The actual number of proper shortest paths is unknown, so we start with a really great value for 'k'. 
YCursor pathCursor = ShortestPaths.kShortestPathsCursor(graph, edgeCostsDP, startNode, endNode, Integer.MAX_VALUE);
if (pathCursor.ok())
{
  // The first path between the two nodes having least costs. 
  final EdgeList firstPath = (EdgeList)pathCursor.current();
  final double costsOfFirstPath = calculateCostsForPath(firstPath, edgeCostsDP);

  allShortestPaths.add(firstPath);
  pathCursor.next();

  // Look further. 
  while (pathCursor.ok())
  {
    EdgeList currPath = (EdgeList)pathCursor.current();
    double currCosts = calculateCostsForPath(currPath, edgeCostsDP);
    // If the current path is also a proper shortest path with costs equal to those 
    // of the first path, then add it to the list. 
    if (!(currCosts > costsOfFirstPath))
    {
      allShortestPaths.add(currPath);
      pathCursor.next();
    }
    else
      break;
  }
}

Answer 2

Мы можем выполнить топологическую сортировку, чтобы получить упорядочение вершин ориентированного ациклического графа (DAG). Получив топологический порядок, мы можем применить динамическое программирование, чтобы получить самый длинный путь в DAG.

Пусть индексы вершин после топосорта равны 0,1,2,....,n-1 (всего n вершин в графе)

Пусть F [i] будет значением самого длинного пути, который заканчивается в вершине i.

Тогда для каждого исходящего ребра от i до всех j мы можем обновить F[j] как F[j]=max(F[j],F[i]+1)

Мы можем начать с инициализации всех F [i] в ​​ноль. Затем цикл от i=1 до n-1.

Окончательный ответ будет max{F[i]} 0<=i<=n-1