Aprendizaje Interactivo de Teoría de Grafos
Aprendizaje Interactivo de Teoría de Grafos
Guest User
Using app without sign in
Calculadora de ruta crítica
Identifica la secuencia más larga de tareas dependientes en un cronograma de proyecto, determinando el tiempo más corto posible para completarlo.
Selecciona un algoritmo y genera pasos para comenzar la visualización
El método del camino crítico (CPM) halla la cadena más larga de actividades dependientes en una red de proyecto, que determina la duración mínima del proyecto. Las actividades en este camino crítico tienen holgura cero: cualquier retraso en ellas retrasa todo el proyecto.
El proyecto se modela como un grafo acíclico dirigido de actividades con duraciones. Una pasada hacia adelante en orden topológico calcula el inicio y fin más tempranos de cada actividad; una pasada hacia atrás calcula los tiempos más tardíos que evitan retrasar el proyecto. La diferencia entre el inicio más tardío y el más temprano es la holgura de la actividad, y las actividades con holgura cero forman el camino crítico. Ambas pasadas se ejecutan en O(V + E).
El CPM planifica proyectos de construcción, lanzamientos de software, cambios de línea en fabricación y organización de eventos. Herramientas de gestión de proyectos como Primavera y Microsoft Project calculan caminos críticos de forma continua. Es también una aplicación de libro de texto de los caminos más largos en DAG y la ordenación topológica.
Leer el artículo completo: Operations Research and Graph Theory
Algoritmos relacionados: PERT (Técnica de Evaluación y Revisión de Programas), RCPSP (Programación de Proyectos con Recursos Limitados), Topological Sort