W jaki sposób nazywany jest ten algorytm do znajdowania maksymalnej ścieżki na Directed Acyklical Graph?

Question

Od pewnego czasu używam algorytmu, który działa w złożoności O (V + E) do znalezienia maksymalnej ścieżki na Ukierunkowanym Wykresie Acyklicznym z punktu A do punktu B, który polega na wykonaniu wypełnienia powodziowego w celu znalezienia węzłów dostępne z uwagi A i ile "rodziców" (krawędzi, które pochodzą z innych węzłów) każdego węzła. Potem robię BFS, ale tylko "aktywuję" węzeł, kiedy już użyłem wszystkich jego "rodziców".

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) ; 

Czy istnieje specjalna nazwa tego algorytmu? Powiedziałem to profesorowi informatyki, nazwał to po prostu "Maximum Path on a DAG", ale nie brzmi to dobrze, kiedy mówisz: "Rozwiązałem pierwszy problem z drzewem Fenwick Tree, drugie z Dijkstra, a trzecie z Maksymalna ścieżka ".

Answer 1

Jest to po prostu "najdłuższa ścieżka w DAG", jak wspomnieli inni. Jednak technika, której używasz, w rzeczywistości jest topological sorting z dynamic programming.

Answer 2

Najdłuższa ścieżka w DAG? Pamiętaj, aby wspomnieć o DAG. Znajdowanie najdłuższej ścieżki na ogólnych wykresach to NP-Complete.

Answer 3

Prawdopodobnie nie - ponieważ nie jest to powszechny algorytm. Kiedy potrzebujesz znaleźć ścieżkę w DAG, po prostu ją posortuj, przemierzaj raz i utrzymuj najdłuższą ścieżkę.