С некоторого времени я использую алгоритм, который работает в сложности 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 и третье с Максимальным Путем".
Это просто «самый длинный путь в DAG», как упоминалось другими. Однако метод, который вы используете, на самом деле представляет собой топологическую сортировку с динамическим программированием .
Наверное, нет - потому что это не общий алгоритм. Когда вам нужно найти путь в DAG, вы просто отсортируете его, пройдете один раз и сохраните самый длинный путь.
Самый длинный путь в группе DAG? Убедитесь, что вы упомянули DAG. Нахождение наиболее длинного пути в общих графах является NP-полным.