Parece demasiado complicado, pero funcionaría.
Otro esquema, que me parece más fácil de entender es
Cree un vector de valores M [v] que contenga el máximo de n [v] y el mayor n [x] para cualquier nodo x alcanzable en k pasos.
- ¿Cuáles son las aplicaciones de las tablas hash?
- ¿Por qué los conjuntos en Python tienen una complejidad algorítmica de O (1)?
- ¿Dónde puedo encontrar una biblioteca de estructura de datos de gráficos dirigida, implementada en Javascript?
- ¿Es una matriz que está en un orden ordenado un montón mínimo?
- Visión por computadora: ¿cuáles son los documentos de lectura obligatoria para el algoritmo de seguimiento de objetos?
Comience con k = 0 e inicialice M [v] = n [v]
Recorre todos los nodos y reemplaza M [v] por el máximo (M [v] o M [v] s de sus elementos secundarios).
Repita hasta que no realice ningún cambio.
Si la ruta más larga en el gráfico es k, esto tomará k bucles. Los ciclos de longitud m se resolverán en m pasos.
Esencialmente, los valores n [v] se propagan “arriba” del árbol.
Otra forma es hacer un gráfico con la dirección de los bordes invertidos, luego, para cada nodo, haga DFS para llevar n [v] a los hijos. Si encuentra una n [v] más grande, puede truncar el DFS.
También puede hacer esto con álgebra matricial si lo desea. Cree una matriz E de los bordes, luego inicialice el vector M = n. establece la matriz A = E o I (creando autoenlaces si no existen). Entonces el algoritmo establece M = A max M en cada paso. La operación máxima es como la multiplicación de matrices, excepto que en lugar del producto interno, elige el valor más grande en el vector en lugar de la suma.
