Как вычислить критический путь направленного ациклического графа?

Question

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

Например, если я иметь следующую структуру:

  Node A (weight 3) 
      /   \ 
    Node B (weight 4)  Node D (weight 7) 
    /    \ 
Node E (weight 2) Node F (weight 3) 

Критический путь должен быть А-> B-> F (общий вес: 10)

Answer 1

У меня нет понятия о «критической пути ", но я предполагаю, что вы имеете в виду this.

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

Если вы собираетесь часто запрашивать, вы можете также увеличить границы между узлами информацией о весе их поддеревьев при вставке. Это относительно дешево, а повторный обход может быть чрезвычайно дорогим.

Но вам нечего спасать вас от полного обхода, если вы этого не сделаете. Порядок не имеет значения, если вы совершаете обход и никогда не идите по тому же пути дважды.

Answer 2

Я бы решил это с помощью динамического программирования. Чтобы найти максимальную стоимость от S до T:

• Топологический сортировать узлы графа, как S = x_0, x_1, ..., x_n = Т. (игнорировать любые узлы, которые могут достигать S или быть достигнуты с Т.)
• максимальная стоимость от S до S является вес S.
• Предполагая, что вы вычислили максимальную стоимость от S до x_i для всех я < к, максимальная стоимость от S до x_k является стоимость от x_k плюс максимальная стоимость для любого узла с ребром до x_k.

Answer 3

Попробуйте метод A *.

A* Search Algorithm

В конце концов, чтобы иметь дело с листьями, просто сделать все они ведут к конечной точке, чтобы установить в качестве цели.

Answer 4

Существует бумага, которая имеет алгоритм для этого: «Критический путь в сети действий с временными ограничениями». К сожалению, я не смог найти ссылку на бесплатную копию. Короче говоря, я могу только заострить идею изменения http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm или http://en.wikipedia.org/wiki/A *

ОБНОВЛЕНИЕ: Приносим извинения за дерьмовое форматирование - механизм уценки на стороне сервера, по-видимому, сломан.

Answer 5

Мой первый ответ, пожалуйста, простите за любую нестандартную вещь культурой stackoverflow.

Я думаю, что решение прост. Просто отрицайте веса и запускайте классический самый короткий путь для DAG (конечно, для весов вершин). Он должен работать довольно быстро.(Временная сложность O (V + E) может быть)

Я думаю, что это должно сработать так, как если бы вы отменили весы, самая большая из них станет самой маленькой, вторая по величине будет второй по величине и так далее, как если бы a > b, то -a < -b , Тогда запуск DAG должен быть достаточным, так как он найдет решение для наименьшего пути отрицательного и, таким образом, найдет самый длинный путь для исходного кода