Actualmente estoy trabajando en el método para encontrar el camino más largo en los grafos acíclicos dirigidos (DAC's). Me pregunto si hay otra forma de hacerlo que no sea la ordenación topológica. ¿Hay alguna posibilidad de utilizar la matriz de adyacencia para resolver este problema?
Respuesta
¿Demasiados anuncios?
Daniel G
Puntos
12647
En primer lugar, permíteme decir que encontrar el camino más largo en un DAC utilizando la ordenación topológica funciona muy bien, y me pregunto por qué buscas métodos alternativos. La ordenación topológica en sí misma se puede hacer en tiempo lineal, y encontrar el camino más largo utilizando la ordenación topológica también funciona en tiempo lineal, lo que te da un algoritmo muy rápido (que es bastante inusual para este tipo de problemas).
En segundo lugar, supongo que se puede mirar la matriz de adyacencia para calcular el camino más largo, y yo lo haría de la siguiente manera. Digamos que he dado una matriz de adyacencia, por ejemplo
$$\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ \end{bmatrix} $$
El algoritmo funciona como sigue. Se toma la primera fila de la matriz y se encuentra el primer 1 de esa fila. Cuando no hay 1, significa que no hay ninguna arista de salida desde el primer vértice del gráfico. Registra que el camino más largo que parte de la fila 1 fue 0 . Pasa a la siguiente fila.
Encuentra el primer 1 de la segunda fila. Este aparece en la columna 3. Por lo tanto, pasar a la fila 3 y encontrar el primer 1. Este aparece en la columna 1, que ya hemos cubierto, y de la que el camino más largo era 0. Esto da un camino de longitud total 2. Pasar al siguiente 1 en la fila 3. Esto lleva a la fila 4, que no lleva a ninguna parte, de nuevo un camino de longitud total 2. El siguiente 1 en la fila 3 lleva a la fila 5, que no lleva a ninguna parte. En total, puedo obtener un camino de longitud 2 de la fila 2. Pase a la fila 3.
Nota que ya cubrimos la fila 3 al comprobar la fila 2, y descubrimos que el camino más largo tenía una longitud 1 para esta fila. Pase a la fila 4.
La fila 4 no tiene ningún 1, así que registra un 0 como el camino más largo a partir de esta fila. Pasa a la fila 5.
La fila 5 tampoco tiene 1's, así que registra un 0 . Ve a la fila 6.
El primer 1 de la fila 6 aparece en la columna 4, así que comprobamos lo que hemos registrado en la fila 4, que era un 0. Esto da, por tanto, una longitud de camino de 1. El segundo 1 de la fila 6 lleva a la fila 8, así que pasamos a la fila 8. Esta fila tiene un 1 en la columna 5, que ya hemos registrado como un camino de longitud 0 como su camino más largo, así que registramos un 2 . Pasa a la fila 7.
El primer 1 aparece en la columna 3, donde registramos un 1. Por tanto, el camino más largo hasta ahora en esta fila es el 2. Pasamos al siguiente 1, que aparece en la fila 8. De hecho, ya cubrimos la fila 8 en los pasos que dimos para la fila 6, y encontramos un camino de longitud máxima de 1. Así que puedo registrar un 2 para la fila 7. Pase a la fila 8.
La fila 8 ya ha sido cubierta, y registramos un 1.
Ahora sólo tengo que tomar el valor máximo de todas las longitudes de trayectoria que he registrado en cada fila. Este valor es 2, y podría obtenerse a partir de los vértices 2, 6 y 7.
Así es como yo lo haría. Tenga en cuenta que el algoritmo se vuelve cada vez más sencillo de llevar a cabo cuantas más filas haya cubierto, ya que está registrando más y más longitudes de caminos máximos mientras recorre las filas.
