ALGORITMO DE DIJKSTRA
MATEMÁTICA DISCRETA
1
EDSGER WYDE DIJKSTRA
Nacido en Rotterdam, (Holanda) en 1930, su padre era químico y su
madre matemática. con 12 años, entró en Gymnasium Erasminium,
una escuela para estudiantes especialmente brillantes, donde dio
clases de Griego, Latín, Francés, Alemán, Inglés, biología, matemáticas
y química.
En 1959, Dijkstra anunció su algoritmo de caminos mínimos o también llamado
ruta mas corta o árbol mínimo o simplemente algoritmo de Dijkstra es un
algoritmo para determinar el camino o ruta mas corta desde un nodo de origen
hacia los demás nodos del grafo, en el cual cada arista o arco posee un peso.
PASOS PARA SU APLICACIÓN
Para realizar la aplicación del algoritmo de Dijkstra, se aplican los siguientes pasos:
1. Se elige un nodo de inicio al cual se le marcara un peso de la siguiente forma:
[X,Y](N)
Donde ‘X’ equivale a el valor del recorrido actual de los arcos, ‘Y’ equivale a el nodo predecesor o de origen y ‘N’
al numero de iteración u operación actual.
2. A los nodos adyacentes del nodo seleccionado como nodo de inicio, se deben asignar un peso de igual
forma al punto anterior, ( [X,Y](N) )
3. De los nodos con los pesos calculados se toma el nodo con menor valor en X y este será el siguiente a visitar
4. Los pasos 2 y 3 deben repetirse teniendo en cuenta que si al intentar calcular los pesos para los nodos
adyacentes a un nodo que esta siendo visitado, uno de estos ya tiene un peso asignado, deben calcularse los
demás pesos cuantas veces sean necesario, y siempre se tomara el peso mínimo calculado
5. Los nodos pueden ser visitados una sola vez
Aplicaciones:
Encaminamiento de paquetes por los routers: En un momento dado, un mensaje puede tardar
cierta cantidad de tiempo en atravesar cada línea (por ejemplo, por efectos de congestión). En este
caso, tenemos una red con dos nodos especiales, el de inicio y el de llegada. Los pesos de las aristas
serían los costes. El objetivo del algoritmo es encontrar un camino entre estos dos nodos cuyo coste
total sea el mínimo.
Aplicaciones para Sistemas de información geográficos: extracción de características
curvilíneas de imágenes usando técnicas de minimización del camino: La imagen se
representa como una matriz de puntos, cada uno con una intensidad. Cada nodo es un punto (píxel)
de la imagen. El peso de las aristas es la diferencia de color.
Reconocimiento de lenguaje hablado: Se puede construir un grafo cuyos vértices correspondan a
palabras posibles y las aristas unan palabras que pueden ir colocadas al lado de las otras. Si el peso de
las aristas corresponde a la probabilidad de que estén así colocadas, el camino más corto en el grafo
será la mejor interpretación de la frase.
Enrutamiento de aviones y tráfico aéreo: Consiste en un agente de solicitudes de viaje software
para hacer un programa de vuelos para los clientes. El agente tiene acceso a una base de datos con
todos los aeropuertos y los vuelos como el número de vuelo, el aeropuerto de origen y destino y los
horarios de salida y de llegada. La aplicación se usa para determinar la hora de llegada más temprana
para el destino dado un aeropuerto de origen y hora de inicio.
Tratamiento de imágenes médicas.
Movilidad terrestre
Ejemplo 1
La administración de del parque de las leyendas necesita encontrar la ruta más
corta desde la entrada del parque (nodo O) hasta el mirador (nodo T) a través del
sistema de caminos que se presenta en la figura siguiente:
Métodos de solución:
Un método sencillo para aprender a enfrentar este problema es el de la fuerza bruta.
Fuerza bruta: consiste en explorar cada uno delos caminos posibles a fin de determinar cuál es el mejor.
En el grafo anterior resulta bastante sencillo determinar todas las soluciones posibles.
Podríamos seguir así enumerando cada una de las rutas, hasta ahora la mínima es de 13u.
Otro método mucho más rápido y eficiente para resolver este tipo de problemas es el
Algoritmo de Dijkstra.
Vamos a resolver el Ejemplo anterior para determinar la ruta más corta desde “O” hasta “T”
utilizando el Algoritmo de Dijkstra
Iteración 01: procedemos a etiquetar el nodo origen y lo convertimos en permanente, luego
etiquetamos los nodos adyacentes, directamente conectados que serán denominados nodos
temporales.
Iteración 02: de alguno de los nodos temporales elegimos aquel que tenga el menor costo total
asociado y lo convertimos en permanente y actualizamos los nodos temporales.
Iteración 03:
Iteración 04:
Ejemplo 02
Una persona tiene que trasladarse a diario del pueblo A al pueblo H. está estudiando cual es el
trayecto más corto usando un mapa de carreteas.
Las carreteras y sus distancias están representadas en la siguiente matriz:
Ejercicio 03
Determine la ruta más corta entre los nodos O y T de la
siguiente red.
https://youtu.be/5w24KUccs5o
Ejercicio 04
Determine la ruta más corta entre los nodos O y T de la siguiente red.
https://youtu.be/fmC3D36x7Qw
Ejercicio 04
Determine la ruta más corta entre los nodos 1 y 8 de la siguiente red.
Ejercicio 05
Determine la ruta más corta entre los nodos 1 y 7 de la
siguiente red.
Algoritmo de Dijkstra
Dijkstra(G, f)
S = { f }, C = { V }
d[f] = 0
d[u] = u f
while (C ) {
seleccionar vértice w C / d[w] es mínimo
S = S {w}, C = C - {w}
for cada vertex v Adyacente[w] {
if (d[v] > d[w] + w(w, v))
d[v] = d[w] + w(w, v)
}
}
