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?

Icono de iDevice 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.

 


Icono de iDevice 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.

Icono IDevice Objetivos
En el apartado anterior hemos hablado de que existe un algoritmo que resuelve estos problemas, el algoritmo de  Dijkstra. En este vídeo se cuenta de manera fácil cómo funciona y los pasos que hay que seguir, aunque claro, todo será más complicado cuantos más vértices haya.
 

Para terminar este apartado vamos a resolver un problema que plantearon a Luisa y Pedro en la empresa TRANS VELOX, para ocupar el puesto de Juan y otro de "Los Puentes de la dársena del Guadalquivir".
Icono de iDevice 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.