¿Cómo se llama este algoritmo para buscar la ruta máxima en un gráfico acíclico dirigido?

Question

Desde hace algún tiempo, estoy usando un algoritmo que se ejecuta en complejidad O (V + E) para encontrar la ruta máxima en un Gráfico acíclico dirigido del punto A al punto B, que consiste en realizar un llenado de inundación para encontrar qué nodos accesible desde la nota A, y cuántos "padres" (bordes que provienen de otros nodos) tienen cada nodo. Luego, hago un BFS pero solo "activando" un nodo cuando ya había usado todos sus "padres".

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

¿Hay algún nombre especial para este algoritmo? Se lo comenté a un profesor de Informática, que acaba de llamarlo "Ruta máxima en un DAG", pero no suena bien cuando dices "Resolví el primer problema con un Fenwick Tree, el segundo con Dijkstra, y el tercero con Ruta máxima ".

Answer 1

El es simplemente el "Camino más largo en un DAG" como otros mencionaron. Sin embargo, la técnica que está usando es realmente topological sorting con dynamic programming.

Answer 2

¿La ruta más larga en un DAG? Asegúrate de mencionar DAG. Encontrar una ruta más larga en gráficos generales es NP-Complete.

Answer 3

Probablemente no, porque no es un algoritmo común. Cuando necesitas encontrar una ruta en DAG, solo tienes que ordenarla, atravesar una vez y mantener el camino más largo.