Algoritmo de Dijkstra

Algoritmo de Dijkstra
	; Ejecución del algoritmo de Dijkstra
Tipo	Algoritmo de búsqueda
Problema que resuelve	Problema del camino más corto
Estructura de datos	Grafo
Creador	Edsger Dijkstra
Fecha	1959
Clase de complejidad	P
Tiempo de ejecución
Peor caso
	[editar datos en Wikidata]

El 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, hacia el resto de los vértices en un grafo que tiene pesos en cada arista. Su nombre alude a Edsger Dijkstra, científico de la computación de los Países Bajos que lo concibió en 1956 y lo publicó por primera vez en 1959.^[1]^[2]

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen hasta el resto de los vértices que componen el grafo, el algoritmo se detiene. Se trata de una especialización de la búsqueda de costo uniforme y, como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).^[3]

Algoritmo

Teniendo un grafo dirigido ponderado de $N$ nodos no aislados, sea $x$ el nodo inicial. Un vector $D$ de tamaño $N$ guardará al final del algoritmo las distancias desde $x$ hasta el resto de los nodos.

Inicializar todas las distancias en $D$ con un valor infinito relativo, ya que son desconocidas al principio, exceptuando la de $x$ , que se debe colocar en $0$ , debido a que la distancia de $x$ a $x$ sería $0$ .
Sea $a=x$ (Se toma $a$ como nodo actual).
Se recorren todos los nodos adyacentes de a, excepto los nodos marcados. Se les llamará nodos no marcados v_i.
Para el nodo actual, se calcula la distancia tentativa desde dicho nodo hasta sus vecinos con la siguiente fórmula: dt(v_i) = D_a + d(a,v_i). Es decir, la distancia tentativa del nodo ‘v_i’ es la distancia que actualmente tiene el nodo en el vector D más la distancia desde dicho nodo ‘a’ (el actual) hasta el nodo v_i. Si la distancia tentativa es menor que la distancia almacenada en el vector, entonces se actualiza el vector con esta distancia tentativa. Es decir, si dt(v_i) < D_vi → D_vi = dt(v_i)
Se marca como completo el nodo a.
Se toma como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y se regresa al paso 3, mientras existan nodos no marcados.

Una vez terminado al algoritmo, $D$ estará completamente lleno.

Complejidad

Orden de complejidad del algoritmo:

O(|V|²+|A|) = O(|V|²), sin utilizar cola de prioridad, :O((|A|+|V|) log |V|) = O(|A| log |V|) utilizando cola de prioridad (por ejemplo, un montículo binario o un árbol binario balanceado). Por otro lado, si se utiliza un montículo de Fibonacci, sería O(|V| log |V|+|A|).

La complejidad computacional del algoritmo de Dijkstra se puede calcular contando las operaciones realizadas:

El algoritmo consiste en n-1 iteraciones, como máximo. En cada iteración, se añade un vértice al conjunto distinguido.
En cada iteración, se identifica el vértice con la menor etiqueta entre los que no están en S_k. El número de estas operaciones está acotado por n-1.
Además, se realizan una suma y una comparación para actualizar la etiqueta de cada uno de los vértices que no están en S_k.

Luego, en cada iteración se realizan a lo sumo 2(n-1) operaciones.

Entonces:

Teorema: El algoritmo de lpz realiza O(n²) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.

En general:

Tiempo de ejecución = O(|A|.𝑻_𝒅𝒌+|v|.𝑻_𝒅𝒎)

|A|: Número de aristas

𝑻_𝒅𝒌: Complejidad de disminuir clave

|V|: Número de vértices

𝑻_𝒅𝒎: Complejidad de extraer mínimo

Pseudocódigo

Estructura de datos auxiliar: Q = Estructura de datos cola de prioridad (se puede implementar con un montículo)

   DIJKSTRA (Grafo G, nodo_fuente s)       
       para u ∈ V[G] hacer
           distancia[u] = INFINITO
           padre[u] = NULL
           visto[u] = false
       distancia[s] = 0
       adicionar (cola, (s, distancia[s]))
       mientras que cola no es vacía hacer
           u = extraer_mínimo(cola)
           visto[u] = true
           para todos v ∈ adyacencia[u] hacer
               si ¬ visto[v]      
                   si distancia[v] > distancia[u] + peso (u, v) hacer
                       distancia[v] = distancia[u] + peso (u, v)
                       padre[v] = u
                       adicionar(cola,(v, distancia[v]))

Otra versión en pseudocódigo sin cola de prioridad

función Dijkstra (Grafo G, nodo_salida s)
  //Usaremos un vector para guardar las distancias del nodo salida al resto
  entero distancia[n] 
  //Inicializamos el vector con distancias iniciales
  booleano visto[n] 
  //vector de boleanos para controlar los vértices de los que ya tenemos la distancia mínima
  para cada w ∈ V[G] hacer
     Si (no existe arista entre s y w) entonces
         distancia[w] = Infinito //puedes marcar la casilla con un -1 por ejemplo
     Si_no
         distancia[w] = peso (s, w)
     fin si 
  fin para
  distancia[s] = 0
  visto[s] = cierto
  //n es el número de vértices que tiene el Grafo
  mientras que (no_estén_vistos_todos) hacer 
     vértice = tomar_el_mínimo_del_vector distancia y que no esté visto;
     visto[vértice] = cierto;
     para cada w ∈ sucesores (G, vértice) hacer
         si distancia[w]>distancia[vértice]+peso (vértice, w) entonces
            distancia[w] = distancia[vértice]+peso (vértice, w)
         fin si
     fin para 
  fin mientras
fin función.

Al final, tenemos en el vector distancia en cada posición la distancia mínima del vértice salida a otro vértice cualquiera.

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 óptima de dicho modelo.

Véase también

Referencias

↑ Frana, Phil (August 2010). «An Interview with Edsger W. Dijkstra». Communications of the ACM 53 (8): 41-47. doi:10.1145/1787234.1787249.
↑ Dijkstra, E. W. (1959). «A note on two problems in connexion with graphs». Numerische Mathematik 1: 269-271. S2CID 123284777. doi:10.1007/BF01386390.
↑ Knuth, D.E. (1977). «A Generalization of Dijkstra's Algorithm». Information Processing Letters 6 (1): 1-5. doi:10.1016/0020-0190(77)90002-3.

Enlaces externos

Wikimedia Commons alberga una galería multimedia sobre Algoritmo de Dijkstra.
Wikilibros alberga un libro o manual sobre algoritmo de Dijkstra.
Presentación del algoritmo de Dijkstra
Video del algoritmo de Dijkstra
Applets en Java para probar el algoritmo de Dijkstra (en inglés)
Graph módulo Perl en CPAN
Bio::Coordinate::Graph módulo Perl en CPAN que implementa el algoritmo de Dijkstra
Algoritmo de Dijkstra en Javascript. Resolución en línea del algoritmo de Dijkstra.
Optimización del algoritmo del camino más corto entre todos los nodos de un grafo no dirigido. Comparación entre el algoritmo de Dijkstra y el de Floyd-Warshall, y método para optimizar el primero.
Distintas implementaciones del algoritmo en RosettaCode.org
Algoritmo de Dijkstra en PHP

Datos: Q8548
Multimedia: Dijkstra's algorithm / Q8548

[Dijkstra_Interview-1] Frana, Phil (August 2010). «An Interview with Edsger W. Dijkstra». Communications of the ACM 53 (8): 41-47. doi:10.1145/1787234.1787249.

[Dijkstra1959-2] Dijkstra, E. W. (1959). «A note on two problems in connexion with graphs». Numerische Mathematik 1: 269-271. S2CID 123284777. doi:10.1007/BF01386390.

[3] Knuth, D.E. (1977). «A Generalization of Dijkstra's Algorithm». Information Processing Letters 6 (1): 1-5. doi:10.1016/0020-0190(77)90002-3.

[1]

[2]

[3]

Algoritmo de Dijkstra
Ejecución del algoritmo de Dijkstra
Tipo	Algoritmo de búsqueda
Problema que resuelve	Problema del camino más corto
Estructura de datos	Grafo
Creador	Edsger Dijkstra
Fecha	1959
Clase de complejidad	P
Tiempo de ejecución
Peor caso	$O(\|E\|+\|V\|\log \|V\|)\,$
[editar datos en Wikidata]