¿Ordenación topológica para la ruta más larga en un DAG?

Answer

1. 

   davy.ai

   July 17, 2023 at 2:20 pm

   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:

   import java.util.*;
   
   public class LongestPath {
       static int longestPath(ArrayList<><integer>> graph, int source, int destination) {
           // Crear una lista para almacenar la distancia de todos los vértices desde el vértice fuente
           int[] dist = new int[graph.size()];
   
           // Inicializar la distancia de todos los vértices desde el vértice fuente como -1
           Arrays.fill(dist, -1);
   
           // Establecer la distancia del vértice fuente desde sí mismo como 0
           dist[source] = 0;
   
           // Crear una cola para ordenamiento topológico
           LinkedList<integer> queue = new LinkedList<integer>();
   
           // Agregar el vértice fuente a la cola
           queue.add(source);
   
           // Ordenamiento topológico
           while (!queue.isEmpty()) {
               int u = queue.remove();
               for (int v : graph.get(u)) {
                   if (dist[v] < dist[u] + 1) {
                       dist[v] = dist[u] + 1;
                       queue.add(v);
                   }
               }
           }
   
           // Devolver la distancia del vértice destino desde el vértice fuente
           return dist[destination];
       }
   
       public static void main(String[] args) {
           // Crear un grafo de ejemplo
           ArrayList<><integer>> graph = new ArrayList<>();
           graph.add(new ArrayList<integer>(Arrays.asList(1)));
           graph.add(new ArrayList<integer>(Arrays.asList(2, 3)));
           graph.add(new ArrayList<integer>());
           graph.add(new ArrayList<integer>(Arrays.asList(4)));
           graph.add(new ArrayList<integer>());
   
           // Encontrar el camino más largo desde el vértice 1 al vértice 4
           int longestPath = longestPath(graph, 1, 4);
           System.out.println("Camino más largo: " + longestPath);
       }
   }
   

   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 en dist[u] + 1 en lugar de dist[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.

Comments are closed.