Diseñaremos un analizador de red logística que reutiliza una misma estructura para responder preguntas diferentes: conectividad, ruta mínima, infraestructura básica, capacidad de transporte y tolerancia a fallos.
Una empresa opera centros logísticos conectados por rutas bidireccionales. Cada conexión posee distancia y capacidad máxima.
El sistema debe analizar la red, visualizar resultados y comparar el funcionamiento normal con escenarios de fallo.
Cada centro es un vértice. Cada ruta es una arista no dirigida con dos atributos numéricos.
La distancia se usa para caminos mínimos y MST; la capacidad se usa para flujo.
La misma arista tiene diferentes significados según la pregunta:
| Análisis | Valor usado | Objetivo |
|---|---|---|
| Ruta | Distancia | Minimizar recorrido |
| MST | Distancia o costo de instalación | Conectar con costo total mínimo |
| Flujo | Capacidad | Maximizar transporte |
| Resiliencia | Topología | Mantener conectividad ante fallos |
El laboratorio contiene siete centros y once rutas. Los datos son pequeños para poder inspeccionar los resultados, pero la arquitectura separa modelo, algoritmos y vista.
const ruta = {
origen: "C",
destino: "D",
distancia: 3,
capacidad: 4
};Ejecuta cada análisis. Luego falla C–D y vuelve a calcular la ruta para observar cómo la alternativa aumenta la distancia.
Conexiones seleccionadas
Resultado
Interpretación
Antes de ejecutar algoritmos se comprueba:
BFS o DFS desde cualquier centro debe visitar los siete vértices. Si no ocurre, las rutas y flujos entre componentes son imposibles.
La conectividad es una precondición útil antes de calcular un árbol generador.
Dijkstra usa la distancia de cada ruta. En el escenario normal obtiene A–C–D–F–G con costo 12.
La ruta se reconstruye mediante predecesores; no basta con devolver solamente el costo.
Kruskal selecciona seis rutas para conectar los siete centros con costo total 15.
El MST minimiza infraestructura, pero elimina redundancia; no debe confundirse con la red operativa más resiliente.
Para el flujo, cada ruta bidireccional se modela con capacidad en ambos sentidos y se aplican caminos aumentantes. Entre A y G, Edmonds–Karp obtiene un flujo máximo de 11 unidades.
El resultado mide capacidad agregada bajo el modelo, no garantiza que una política logística real permita dividir envíos de esa manera.
Al retirar C–D, la red continúa conectada, pero la ruta mínima cambia a A–C–E–G y aumenta de 12 a 14. En este caso, el flujo máximo se mantiene en 11: un fallo puede degradar una métrica sin afectar otra.
Repetir la simulación para cada arista produce un ranking de criticidad.
Puentes y vértices de corte revelan fallos que desconectan la red. Sin embargo, un enlace también puede ser crítico por aumentar mucho costos o reducir capacidad aunque no desconecte.
La resiliencia debe evaluar conectividad, degradación de rutas y pérdida de flujo.
class RedLogistica {
agregarCentro(centro) { /* modelo */ }
agregarRuta(ruta) { /* modelo */ }
validar() { /* reglas del dominio */ }
}
function rutaMinima(red, origen, destino) { /* algoritmo */ }
function dibujarRed(red, resultado) { /* vista */ }Separar capas permite probar algoritmos sin canvas y cambiar la interfaz sin reescribir el modelo.
Cada algoritmo necesita casos pequeños con respuestas conocidas y pruebas de integración sobre la red completa.
| Análisis | Implementación | Tiempo |
|---|---|---|
| Conectividad | BFS/DFS | O(V+E) |
| Ruta | Dijkstra con montículo | O((V+E) log V) |
| MST | Kruskal | O(E log E) |
| Flujo | Edmonds–Karp | O(VE²) |
La interfaz debe explicar qué representa cada color, peso y resultado. Un valor sin unidades o una ruta sin costo es difícil de interpretar.
Los controles deben reiniciar correctamente el estado y anunciar cambios para tecnologías de asistencia.
La teoría de grafos ofrece mucho más que una colección de algoritmos. Proporciona una forma de modelar relaciones, formular preguntas precisas y elegir estructuras que convierten problemas reales en cálculos verificables.
El paso siguiente consiste en aplicar estas técnicas a datos propios: comenzar con un modelo pequeño, validar cada resultado y ampliar la solución solo cuando las preguntas del dominio lo requieran.