Ruta más corta entre dos nodos específicos
Encontrar la ruta más corta entre dos nodos específicos en una red de optimización, es un proeblema en el que el objetivo es minimizar el costo total .
A este problema se le puede asignar la siguiente red:
R= [x,A,d]
x= conjunto de nodos
A= conjunto de aristas
d= distancias de costos asociados a las aristas.
Para que un problema tenga solución de ruta más corta entre dos nodos específicos, debe cumplir con:
-
Al menos exista un camino entre s y t
-
No debe haber circuitos negativos
El modelo de programación lineal correspondiente a rutas más cortas tiene características similares a los problemas de transbordo, por ejemplo:
-
Se minimiza siempre el modelo, ya que como el nombre lo dice, buscamos obtener la ruta más corta, es decir, la ruta con menos distancia.
-
Cada nodo es una restricción.
-
Dentro de las restricciones se pondrá un flujo que entra y un flujo que sale.
-
Cada arista es una variable.
En los problemas de ruta más corta entre dos nodos específicos nos poderemos encontrar con diferentes tipos de problemas, tales como:
-
Problema de reemplazo
-
Ruta más segura
-
Problema tipo mochila
-
Problema de planeación de producción
-
Programación dinámica
Para resolver este tipo de problemas se pueden utilizar el algoritmo de Dijkstra.
El algoritmo de Dijkstra etiqueta de manera permanente los nodos sin analizar otros posibles caminos.
Características del método de Dijkstra:
-
Trabaja con redes dirigidas.
-
Solo acepta costos positivos
-
Trabaja con etiquetas temporales
-
Trabaja con etiquetas permanentes. (El nodo inicial siempre estará marcado con etiquetas permanentes)
Etiquetas temporales
(d(x) , a(x))
[d(x) , a(x)]
Etiquetas permanentes
Donde d(x) es la distancia y a(x) es el nodo antecesor.
Ejemplo: Considere la siguiente red, siendo A el nodo inicial y H el nodo final, y resuelva por Dijkstra. Plantear el M.P.L
Lo primero que hay que hacer es etiquetar permanentemente el primer nodo, en este caso el nodo A.
Posteriormente etiquetamos temporalmente los nodos que le siguen,sumando las distancias, hasta que todos los nodos estén etiquetados temporalmente.
[0,-]
(3,A)
(1,A)
(8,B)
(4,B)
[3,C]
(6,C)
[5,D]
(7,D)
(10,G)
(8,F)
(8,E)
Posteriormente lo que hay que hacer es etiquetar permanentemente los nodos que no tengan dos rutas, y en dado caso que tengan dos etiquetas temporales, elegir la más pequeña.
[0,-]
[1,A]
[3,A]
[8,B]
[3,C]
[5,D]
[7,D]
[8,E,F]
El método acaba cuando el nodo final está etiquetado permanentemente.
En este caso, podemos observar que hay dos nodos que nos llevan a la solución, lo cual quiere decir que hay múltiple solución, además, que la ruta más corta tiene como distancia 8.