Algoritmo de Dijkstra

Algoritmo de Dijkstra. También llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. 

Aplicaciones

En múltiples aplicaciones donde se aplican los grafos, es necesario conocer el camino de menor costo entre dos vértices dados:

• Distribución de productos a una red de establecimientos comerciales.
• Distribución de correos postales.
• Sea G = (V, A) un grafo dirigido ponderado.

El problema del camino más corto de un vértice a otro consiste en determinar el camino de menor costo, desde un vértice u a otro vértice v. El costo de un camino es la suma de los costos (pesos) de los arcos que lo conforman.

Características del algoritmo

• Es un algoritmo greddy.
• Trabaja por etapas, y toma en cada etapa la mejor solución sin considerar consecuencias futuras.
• El óptimo encontrado en una etapa puede modificarse posteriormente si surge una solución mejor.

Pasos del algoritmo

Algoritmo 24.1: Algoritmo de Dijkstra. Inicialización.

• Sea V un conjunto de vértices de un grafo.
• Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v.
• Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo.
• Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v.
• Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido.
• Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices.

Formulación del algoritmo Dijkstra

Para llevar a cabo la formulación de un modelo de red con el algoritmo Dijkstra es necesario saber de los nodos de inicio, de final y de transbordo de la red, posteriormente se analizan las etiquetas que se presentan en los arcos de la red, para así poder determinar la función objetivo del problema a formular.

En el siguiente ejemplo se presenta la formulación del modelo de Red de "Ejecución del algoritmo de Dijkstra"

Se formulan las variables de decisión denominadas Xij, que son variables binarias y determinan la activación del arco que conecta el nodo i con j.

En la red que "Ejecución del algoritmo de Dijkstra" las variables de decisión del problema son: X₁₂,X₁₃,X₁₆,X₂₃,X₂₄,X₃₆,X₃₄,X₆₅,X_45.

Posteriormente se plantea la función objetivo que consiste en tomar la ruta que genere el menor valor de etiquetas de toda la red a través de arcos que conectan los nodos.

Función Objetivo= Minimizar 7*X₁₂+9*X₁₃+ 14*X₁₆+10*X₂₃+15*X₂₄+2*X₃₆+11*X₃₄+9X₆₅+6X₄₅

Restricciones del problema. Para llevar a cabo el desarrollo de las restricciones del problema es necesario conocer el nodo de inicio, que en el caso de la red es el nodo 1, el nodo final que es el nodo 5 y los nodos de transbordo que son 2,3,4 y 6. Una vez identificados los nodos de la red se plantean las restricciones del problema

Restricciones del nodo inicial y final: También denominadas restricciones de oferta y demanda en algunos modelos de formulación. Estas restricciones le indican al modelo que solo debe tomar un arco que sale del nodo inicial y un arco que llega al nodo final, esto con el objetivo de garantizar que se cumplan las condiciones del algoritmo Dijkstra.

En el caso de la formulación del modelo las restricciones del nodo inicial y final son:

Nodo Inicial: X₁₂ +X ₁₃ +X_{16 = 1}

Nodo Final: X₆₅ + X_{45 = 1 .}

Restricciones de nodos transbordo: Estas restricciones también denominadas restricciones de balance, tienen el objetivo de garantizar que todo el flujo que entra en el nodo de transbordo de igual manera debe salir, Estas restricciones se deben generar por cada uno de los nodos de transbordo de la red, en el caso del ejemplo, las restricciones de transbordo son:

Nodo 2: X₁₂₌ X₂₃ +X₂₄

Nodo 3: X₁₃+X₂₃₌ X₃₆+X₃₄

Nodo 4 :X₂₄+X₃₄= X₄₅

Nodo 6 :X₁₆+X₃₆ =X₆₅

Restricciones de no negatividad: Con estas restricciones se garantiza que las variables del modelo no van a tomar valores negativos haciendo que el modelo de infectable.

Una vez planteadas todas las restricciones del modelo que garantice que se va a cumplir el algoritmo de Dijkstra en la red, se procede a resolver el modelo mediante algún software que permita obtener la solución optima de dicho modelo