Grafos ponderados y camino más corto – algoritmo de Dijkstra
MatemáticasConjuntos, lógica y teoría de grafosEdades 16–17
Úsala con tu clase: tus estudiantes la abren con un enlace o un código QR, sin crear una cuenta.
Sigue con Conjuntos, lógica y teoría de grafos
Un mapa de lugares se modela como un grafo: los vértices son lugares, las aristas son carreteras y los pesos son distancias en kilómetros. Elige un vértice de inicio y uno de llegada y avanza paso a paso por el algoritmo de Dijkstra: asigna etiquetas provisionales, fija el vértice con la etiqueta menor y actualiza sus vecinos. Haz clic en una arista para cambiar su longitud (un desvío o una carretera cortada) y observa cómo cambia el camino más corto, junto con los grados de los vértices y la condición para un ciclo euleriano.
Lección: Introducción a la teoría de grafos
Qué muestra
Una red de carreteras puede modelarse como un grafo ponderado: los vértices son lugares, las aristas son vías y cada peso es una distancia en kilómetros. El algoritmo de Dijkstra halla los caminos más cortos desde un vértice de inicio manteniendo una etiqueta provisional de distancia en cada vértice: en cada paso fija el vértice no fijado con la etiqueta menor y actualiza las etiquetas de sus vecinos. Como todos los pesos son positivos, una etiqueta fijada ya no puede mejorar. La simulación muestra también los grados de los vértices, cuya suma es el doble del número de aristas y que, en un grafo conexo, deciden si existen caminos y circuitos eulerianos.
Cómo usarla
Elige un Mapa y selecciona el inicio y el destino en Desde y Hasta. Pulsa Siguiente paso varias veces y pide a los estudiantes que predigan qué vértice se fijará y qué etiquetas cambiarán; usa Paso anterior para revisar una decisión. Compara la ruta final con la que usa menos vías. Después pon Clic en arista para en cortar / abrir vía, corta una vía del camino más corto y pulsa Ejecutar todo para ver la nueva ruta.
Parámetros que puedes cambiar
- Mapa Ciudad (7 lugares), Municipios de una provincia (9 lugares)
- Vértice de inicio
- Vértice de llegada
Preguntas para explorar
- ¿Por qué la etiqueta de un vértice ya no cambia una vez que se ha fijado?
- ¿La ruta con menos aristas es siempre la más corta? ¿Qué ejemplo del mapa lo muestra?
- ¿Qué vías podrías cortar para que las vías restantes sigan conectadas y el grafo tenga un circuito euleriano?
