3.1. El camino más corto
En la Teoría de Grafos, uno de los problemas más conocido es el del camino más corto.
El problema consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.
Para nosotros, los vértices serán poblaciones y los pesos de las aristas el tiempo que empleamos en desplazarnos de un sitio a otro.
La empresa TRANS VELOX es experta en resolver este tipo de problemas, ya que Juan en su juventud, aquel encuentro en la playa con María la Matemática, dio mucho de sí y siempre atento, aprendió mucho de ella, durante los 15 días que pasó en Marbella.
Volviendo al ejemplo del paquete que tenían que enviar desde Sevilla hasta Cádiz, Juan transformó esa situación real en una situación matemática (a esto lo llamamos modelización), después lo resolvió matemáticamente y lo volvió a pasar al mundo real.
¿Cómo crees que lo hizo?
Ejemplo o ejercicio resuelto
Vamos a ver el método que empleó Juan.
Lo primero que hizo, fue coger el mapa y modelizar el problema (dibujar un grafo en un papel como el de abajo).
Donde A representa a Sevilla, B a Los Palacios y Villafranca, C a Utrera, D a Las Cabezas de San Juan, E a Montellano, F a Jerez de la Frontera, G a Villamartín y H a Cádiz.
Los números que hay sobre las aristas (carreteras) representan el tiempo que se tarda en desplazarse de un nodo a otro (de una población a otra).
1. ¿Qué camino tiene que tomar TRANS VELOX para llevar un paquete desde Sevilla a Cádiz?
2. ¿Cuál sería el camino si primero tiene que pasar por Utrera para recoger a un compañero?
Para resolver este tipo de problemas se utiliza el algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos.
Este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen (A:Sevilla) y que llevan al último vértice (H:Cádiz).
Dada la complejidad de dicho algoritmo, nosotros lo resolveremos marcando caminos y realizando las operaciones correspondientes.
AV - Reflexión
¿Te acuerdas de la delegación de TRANS VELOX que había en Morón de la Frontera?
Resulta que acaban de cumplir 25 años desde que abrieron la oficina y han decidido irse a comer a El Coronil.
Estando allí de celebración, reciben una llamada y tienen que desplazarse hasta Olvera.
Calcula cuál será el camino más rápido, utilizando los datos que te mostramos en el siguiente grafo.
 |
 |
Objetivos
AV - Reflexión
En el grafo siguiente, Luisa y Pedro tienen que encontrar el camino más corto (en el sentido de menos “pesado”) entre los vértices a y e.
