Как этот алгоритм, для нахождения максимального пути на Направленном Графике Acyclical, названном?

С некоторого времени я использую алгоритм, который работает в сложности O (V + E) для нахождения максимального пути на Направленном Графике Acyclical от точки для указания на 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", но не звучит хорошим, когда Вы говорите, что "Я решил первую проблему с Деревом Фенвика, второе с Dijkstra и третье с Максимальным Путем".

5
задан Martín Fixman 17 May 2010 в 04:26
поделиться

3 ответа

Это просто «самый длинный путь в DAG», как упоминалось другими. Однако метод, который вы используете, на самом деле представляет собой топологическую сортировку с динамическим программированием .

3
ответ дан 14 December 2019 в 13:28
поделиться

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

2
ответ дан 14 December 2019 в 13:28
поделиться

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

1
ответ дан 14 December 2019 в 13:28
поделиться
Другие вопросы по тегам:

Похожие вопросы: