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	$O(|E|+|V|\log |V|)\,$

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 al resto de los 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.

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, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es 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).

Una de sus aplicaciones más importantes reside en el campo de la telemática, gracias a él, podemos resolver grafos con muchos nodos, los cuales serían muy complicados de hacer sin dicho algoritmo, encontrando así las rutas más cortas entre un origen y todos los destinos en una red.

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 al resto de los nodos.

1. 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.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos nodos no marcados v_i.
4. Para el nodo actual, calculamos la distancia tentativa desde dicho nodo a 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) al nodo v_i. Si la distancia tentativa es menor que la distancia almacenada en el vector, actualizamos el vector con esta distancia tentativa. Es decir: Si dt(v_i) < D_vi → D_vi = dt(v_i)
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos 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). 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 tenemos: TEOREMA: El Algoritmo de Dijkstra 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.

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 no visto[v] y 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.

Otra versión en C del Algoritmo de Dijkstra

#define MAX_NODES 1024 /* número máximo de nodos */
#define INFINITY 1000000000 /* un número mayor que cualquier ruta máxima */
int n, dist[MAX_NODES][MAX_NODES]; /* dist[i][j] es la distancia de i a j */

void shortest_path(int s, int t, int path[])
{
	struct state { /* la ruta en la que se está trabajando */
		int predecessor; /* nodo previo */
		int length; /* longitud del origen a este nodo */
		enum {permanent, tentative} label; /* estado de la etiqueta */
	} state[MAX_NODES];
	struct state *p;
	int i, k, min;
	for (p = &state[0]; p < &state[n]; p++) { /* estado de inicialización*/
		p->predecessor = -1;
		p->length = INFINITY;
		p->label = tentative;
	}
	state[t].length = 0; state[t].label = permanent;
	k = t; /* k es el nodo de trabajo inicial */
	do{ /* ¿hay una ruta mejor desde k? */
		for (i = 0; i < n; i++) /* este grafo tiene n nodos */
			if (dist[k][i] != 0 && state[i].label == tentative) {
				if (state[k].length + dist[k][i] < state[i].length) {
					state[i].predecessor = k;
					state[i].length = state[k].length + dist[k][i];
				}
			}
		/* Encuentra el nodo etiquetado tentativamente con la etiqueta menor. */
		k = 0; min = INFINITY;
		for (i = 0; i < n; i++)
		if (state[i].label == tentative && state[i].length < min) {
			min = state[i].length;
			k = i;
		}
		state[k].label = permanent;
	} while (k != s);
	/* Copia la ruta en el arreglo de salida. */
	i = 0; k = s;
	do {path[i++] = k; k = state[k].predecessor; } while (k >= 0);
}

Prueba de Corección

La prueba del algoritmo de Dijkstra se construye por inducción sobre el número de nodos visitados. Hipótesis invariante: para cada nodo visitado v, dist [v] se considera la distancia más corta desde la fuente hasta v; y para cada nodo no visitado u, se supone que dist [u] es la distancia más corta cuando se viaja solo a través de nodos visitados, desde la fuente hasta u. Esta suposición solo se considera si existe una ruta; de lo contrario, la distancia se establece en infinito. (Nota: no asumimos que dist [u] es la distancia real más corta para nodos no visitados) El caso base es cuando solo hay un nodo visitado, a saber, el origen del nodo inicial, en cuyo caso la hipótesis es trivial. De lo contrario, asuma la hipótesis para n-1 nodos visitados. En cuyo caso, elegimos un borde vu donde u tiene la menor dist [u] de los nodos no visitados y los bordes vu es tal que dist [u] = dist [v] + longitud [v, u]. dist [u] se considera la distancia más corta desde la fuente hacia u porque si hubiera una ruta más corta, y si w fuera el primer nodo no visitado en esa ruta, entonces la hipótesis original dist [w]> dist [u] que crea una contradicción Del mismo modo, si hubiera un camino más corto hacia usted sin usar o sin visitar nodos, y si el último pero un nodo en esa ruta fuera w, entonces habríamos tenido dist [u] = dist [w] + longitud [w, u], también una contradicción. Después de procesar u, seguirá siendo cierto que para cada nodo no visitado w, dist [w] será la distancia más corta desde la fuente hasta el estado de los nodos visitados solamente, porque si hubiera una ruta más corta que no fuera por u, habríamos encontrado anteriormente, y si hubiera una ruta más corta usando u, la habríamos actualizado al procesar u.

Tiempo de ejecución

Los límites del tiempo de ejecución del algoritmo de Dijkstra en un gráfico con los bordes E y los vértices V se pueden expresar como una función del número de aristas, denotado, y el número de vértices, denotados, usando la notación de BigO. Qué tan ajustado sea posible un límite depende de la forma en que se implemente el conjunto de vértices Q. A continuación, los límites superiores se pueden simplificar porque |E| = O (|V|)2 para cualquier gráfico, pero esa simplificación hace caso omiso del hecho de que en algunos problemas, otros límites superiores pueden mantenerse. Para cualquier implementación del conjunto de vértice Q, el tiempo de ejecución es

O (|E|.Tdk + |V|.Tem),

Dónde Tdk y Tem son las complejidades de las operaciones de disminución de clave y extracto en Q, respectivamente. La implementación más simple del algoritmo de Dijkstra almacena el conjunto de vértices Q como una lista o matriz vinculada normal, y extract-minimum es simplemente una búsqueda lineal a través de todos los vértices en Q. En este caso, el tiempo de ejecución es O (|E|+|V|)2 = O (|V|)2. Para gráficos dispersos, es decir, gráficos con mucho menos que |V|2 bordes, el algoritmo de Dijkstra se puede implementar de manera más eficiente almacenando el gráfico en forma de listas de adyacencia y utilizando un árbol de búsqueda binaria autoequilibrante, un montón binario, un montón de emparejamiento o un montón de Fibonacci como una cola de prioridad para implementar la extracción mínima de manera eficiente. Para realizar pasos de disminución de clave en un montón binario de manera eficiente, es necesario utilizar una estructura de datos auxiliares que asocie cada vértice a su posición en el montón, y mantener esta estructura actualizada a medida que cambia la cola de prioridad Q. Con un árbol de búsqueda binaria autoajustable o un montón binario, el algoritmo requiere Ø ((|E| + |V|) log (|V|)) tiempo en el peor de los casos (donde log denota el logaritmo binario log2); para los gráficos conectados este límite de tiempo se puede simplificar a Ø (|E| log (|V|)). El montón Fibonacci mejora esto para O (|E| + |V| log (|V|)) Cuando se utilizan montones binarios, la complejidad del tiempo promedio es menor que el peor de los casos: suponiendo que los costos de borde se extraigan independientemente de una distribución de probabilidad común, el número esperado de operaciones de tecla de disminución está limitado O (|V| log (|E|/|V|)), lo que da un tiempo total de ejecución de O (|E| + |V| log (|E|/|V| log |V|).

Véase también

• Anexo:Ejemplo de Algoritmo de Dijkstra
• Algoritmo de Bellman-Ford

Enlaces externos

• Wikimedia Commons alberga una galería multimedia sobre Algoritmo de Dijkstra.
• Presentación del Algoritmo de Dijkstra
• Video del Algoritmo de Dijkstra
• Applets en Java para probar el algoritmo de Dijkstra (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 online 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