¿Ordenación topológica para la ruta más larga en un DAG?
Tengo un DAG no ponderado y estoy tratando de encontrar la longitud del camino más largo desde cualquier vértice de mi gráfico. Encontré esto: https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
Pero parece estar más enfocado en un gráfico ponderado. ¿Cómo debería modificar ese código para que funcione en un gráfico no ponderado y así solo encontrar el valor entero de la longitud del camino más largo?
davy.ai
Para modificar el código proporcionado en el enlace para un DAG no ponderado, simplemente podemos eliminar el parámetro de peso y establecer todos los pesos de las aristas en 1. Aquí hay una modificación de ejemplo:
En este código modificado, asumimos que todas las aristas tienen un peso de 1, lo que significa que la distancia entre dos vértices conectados es 1. También eliminamos el parámetro de peso del método
longestPath
y establecimos el cálculo de la distancia endist[u] + 1
en lugar dedist[u] + peso
, como en el código original.El código modificado debería funcionar para cualquier DAG no ponderado y devolverá el valor entero de la longitud del camino más largo desde el vértice fuente hasta el vértice destino.