La Ruta Más Corta
Algoritmo de Dijkstra y Modelado PL
Teoría y Etiquetas
El algoritmo de Dijkstra determina la ruta de menor distancia o costo entre un nodo origen específico y los demás puntos de la red. Opera mediante un sistema estructurado de etiquetas de nodo que pueden ser de dos tipos:
Se modifican continuamente si se llega a descubrir una ruta con una distancia acumulada menor hacia ese nodo.
Se fijan una vez que se determina matemáticamente que no existe un camino más corto desde el origen.
Estructura formal de la etiqueta: [uj, i] = [distancia acumulada, nodo predecesor].
Formulación Matemática (PL)
Para modelar la ruta más corta como programación lineal, se asume que ingresa exactamente 1 unidad de flujo en el nodo de origen y debe salir en el nodo de destino final.
xij = 1 si se selecciona y usa el arco que va de i a j.
xij = 0 si el arco no se incluye en la ruta.
Nodo Origen
Flujo de Salida = 1
(Ecuación = 1)
Nodos Intermedios
Entrada - Salida = 0
(Ecuación = 0)
Nodo Destino
Flujo de Entrada = 1
(Ecuación = 1)
Caso Práctico Resuelto: Red de 5 Nodos
Vamos a resolver paso a paso el problema de transbordo desde el Nodo 1 al Nodo 5 utilizando el algoritmo de Dijkstra. Presta atención a cómo las etiquetas pasan de ser temporales (grises) a permanentes (púrpura):
Paso 0: Inicialización
Configuramos el nodo de origen (1) con una etiqueta permanente de distancia 0. Todos los demás nodos inician con distancia infinita [∞, -].
La formulación PL equivalente sería:
min Z = 100x12 + 30x13 + 20x23 + 10x34 + 15x42 + 50x45 + 60x35
Nodo 1 (Origen): x12 + x13 = 1
Nodo 2 (Transbordo): x12 + x42 - x23 = 0
Nodo 3 (Transbordo): x13 + x23 - x34 - x35 = 0
Nodo 4 (Transbordo): x34 - x42 - x45 = 0
Nodo 5 (Destino): x35 + x45 = 1