🚀 Introducción: Optimizando rutas con el Algoritmo de Dijkstra

¿Cómo calcula Google Maps el camino más rápido para llegar a tu destino evitando atascos? ¿Cómo sabe una empresa de reparto qué calles elegir para gastar el mínimo combustible? En el mundo real, los mapas se traducen como grafos valorados o ponderados: redes de puntos (nodos) conectados por líneas (aristas) donde cada línea tiene un número que representa una distancia, un coste o un tiempo de viaje.

Para encontrar el camino óptimo en estas redes complejas, los programadores utilizan el Algoritmo de Dijkstra. Creado por el científico en computación Edsger Dijkstra en 1956, este método funciona de forma "codiciosa" (greedy): explora paso a paso el mapa, asegurándose en cada avance de elegir siempre el camino acumulado más corto y actualizando las previsiones de los nodos vecinos.

Hoy vamos a ayudar a Marta Gema a planificar las visitas a sus cinco amigas (Ana, Beatriz, Carla, Daniela y Elena) saliendo desde su propia casa (nodo O).

🛠️ ¿Cómo funciona esta ficha interactiva?

Esta aplicación es un entorno de aprendizaje guiado. El sistema generará un mapa con distancias totalmente aleatorias y bloqueará o desbloqueará los pasos según vayas respondiendo bien. Sigue estas instrucciones para conseguir tus 10 puntos:

1. Identifícate: Escribe tu nombre y apellidos en la casilla de la barra superior. Si la dejas vacía, no podrás obtener tu nota al final.

2. Paso 1 (Tabla Inicial): Mira las conexiones que salen directamente de la casa de Marta (O). Coloca en la tabla la distancia en metros hacia cada amiga. Si no hay una línea directa desde O hasta alguna de ellas, su distancia inicial es el infinito (inf) y su nodo anterior será un guion (—). Pulsa Verificar Tabla Inicial para avanzar.

3. Paso 2 (Selección del nodo más cercano): El sistema te mostrará la tabla actual de registros. Haz clic sobre la fila de la amiga que tenga la menor distancia acumulada y que todavía no haya sido visitada. Haz clic en Confirmar selección.

4. Paso 3 (Relajación de aristas): Una vez que Marta "viaja" a la casa de esa amiga, debes comprobar si desde allí se descubren atajos más cortos para llegar a las demás. Aplica la fórmula:
   Distancia del nodo actual + Peso de la línea al vecino= Nueva suma
   Si esa suma es menor que la distancia que ya tenías guardada en la tabla para esa vecina, marca la casilla de actualizar, escribe el nuevo valor y selecciona el nodo actual como el nuevo "Anterior". Haz clic en Verificar actualizaciones.

5. Ciclo de juego: La aplicación te irá pidiendo repetir los Pasos 2 y 3 alternativamente hasta que Marta haya visitado todos los nodos del mapa.

6. Finalización y entrega: Al completar el recorrido, aparecerá la tabla con los caminos mínimos definitivos. Ve a la parte inferior de la pantalla, haz clic en 🏁 Finalizar, escribe tu nombre si no lo hiciste, confirma y saca una captura de pantalla del cuadro con tu nota final para subirla a Classroom.