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

Question

С некоторого времени я использую алгоритм сложности O (V + E) для поиска максимального пути на Направленном ациклическом графе от точки A к точке B, который заключается в выполнении заливки, чтобы найти, какие узлы доступны из примечания A, и сколько «родителей» (ребер, которые приходят из других узлов) каждый узел имеет. Затем я выполняю BFS, но только «активирую» узел, когда уже использовал все его «родители».

queue <int> a
int paths[] ; //Number of paths that go to note i
int edge[][] ; //Edges of a
int mpath[] ; //max path from 0 to i (without counting the weight of i)
int weight[] ; //weight of each node

mpath[0] = 0

a.push(0)
while not empty(a)
    for i in edge[a]
        paths[i] += 1
        a.push(i)

while not empty(a)
    for i in children[a]
        mpath[i] = max(mpath[i], mpath[a] + weight[a]) ;

        paths[i] -= 1 ;
        if path[i] = 0
            a.push(i) ;

Есть ли специальное имя для этого алгоритма? Я рассказал об этом профессору информатики, он просто назвал его «Максимальный путь на DAG», но это звучит не очень хорошо, когда вы говорите: «Я решил первую проблему с деревом Фенвика, вторую - с Дейкстрой, а третью - с Максимальный путь ".

Answer 1

Это просто "самый длинный путь в DAG", как упоминали другие. Тем не менее, вы используете метод топологической сортировки с динамическим программированием .

Answer 2

Вероятно, нет - потому что это не обычный алгоритм. Когда вам нужно найти путь в DAG, вы просто сортируете его, проходите один раз и держите самый длинный путь.

Answer 3

Самый длинный путь в DAG? Убедитесь, что вы упомянули DAG. Найти самый длинный путь в общих графах - NP-Complete.