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

Задача имеет оптимальную подструктуру. Чтобы найти самый длинный путь из вершины c в вершину z, нам сначала нужно найти самый длинный путь из c ко всем предшественникам z. Каждая из них представляет собой еще одну меньшую подзадачу (самый длинный путь от c до конкретного предшественника).

Обозначим предшественников z как u1,u2,...,uk и dist[z] как самый длинный путь от c до z, затем dist[z]=max(dist[ui]+w(ui,z))..

Вот иллюстрация с тремя предшественниками, в которых не указаны веса наборов ребер:

Таким образом, чтобы найти самый длинный путь к z, нам сначала нужно найти самый длинный путь к его предшественникам и взять максимум (их значения плюс веса ребер до z).

Это требует, чтобы каждый раз, когда мы посещаем вершину u, все предшественники u были проанализированы и вычислены.

Итак, вопрос: для любой вершины u, как убедиться, что после того, как мы установим dist[u], dist[u] никогда не изменится позже? Скажем иначе: как убедиться, что мы рассмотрели все пути от c до u, прежде чем рассматривать любое ребро, берущее начало в u?

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

Временная сложность: топологическая сортировка занимает O(V+E). В худшем случае, когда z является листом, а все остальные вершины указывают на него, мы посетим все ребра графа, что даст O(V+E).

Пусть f(u) будет максимальной прибылью, которую вы можете получить при переходе от c к u в вашей DAG. Затем вы хотите вычислить f(z). Это можно легко вычислить за линейное время, используя динамическое программирование/топологическую сортировку.

Инициализируйте f(u) = -infinity для каждого u, кроме c, и f(c) = 0 . Затем продолжите вычисление значений f в некотором топологическом порядке вашей DAG. Таким образом, поскольку порядок является топологическим, для каждого входящего ребра вычисляемого узла вычисляются другие конечные точки, поэтому просто выберите максимально возможное значение для этого узла, т. е. f(u) = max( f(v) + cost(v, u)) для каждого входящего ребра (v, u).

Лучше использовать топологическую сортировку вместо Bellman Ford с момента его DAG.

Источник: - http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

ИЗМЕНИТЬ:-

G — это DAG с отрицательными ребрами.

Некоторые преимущества уменьшают вашу прибыль, а некоторые увеличивают вашу прибыль.

• Края - увеличение прибыли - положительное значение
• Края - уменьшение прибыли - отрицательное значение

После TS для каждой вершины U в порядке TS - расслабить каждое выходящее ребро.

dist[] = {-INF, -INF, ….}
dist[c] = 0 // source

for every vertex u in topological order
  if (u == z) break; // dest vertex
  for every adjacent vertex v of u
    if (dist[v] < (dist[u] + weight(u, v))) // < for longest path = max profit
      dist[v] = dist[u] + weight(u, v)

ans = dist[z];