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

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

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

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

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

Спасибо!!


graph directed-acyclic-graphs longest-path
person blazonix    schedule 05.12.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Я думаю, что вы должны сделать, это вычислить все кратчайшие пути от корня до листа, а затем выбрать самый длинный из вычисленных путей. В общем, это будет трудная задача, но, к счастью, вы используете ориентированный ациклический граф. На практике алгоритм будет работать очень хорошо из-за этого ограничения. Вам может помочь следующий код, он был разработан с помощью 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;
  }
}
person Matthias Kricke    schedule 05.12.2012

arrow_upward
2
arrow_downward

Мы можем выполнить топологическую сортировку, чтобы получить порядок вершин ориентированного ациклического графа (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

person nilmish    schedule 28.05.2013