Algoritmo de Dijkstra

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Algoritmo de Dijkstra
Dijkstra Animation.gif
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

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 describió por primera vez en 1959.[cita requerida]

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).[cita requerida]

Una de sus aplicaciones más importantes reside en el campo de la telemática. Gracias a él, es posible resolver grafos con muchos nodos, lo que sería muy complicado resolver sin dicho algoritmo, encontrando así las rutas más cortas entre un origen y todos los destinos en una red.[cita requerida]

Algoritmo[editar]

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.

  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 (Se toma a como nodo actual.)
  3. Se recorren todos los nodos adyacentes de a, excepto los nodos marcados. Se les llamará nodos no marcados vi.
  4. Para el nodo actual, se calcula la distancia tentativa desde dicho nodo hasta sus vecinos con la siguiente fórmula: dt(vi) = Da + d(a,vi). Es decir, la distancia tentativa del nodo ‘vi’ 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 vi. Si la distancia tentativa es menor que la distancia almacenada en el vector, se actualiza entonces el vector con esta distancia tentativa. Es decir, si dt(vi) < Dvi → Dvi = dt(vi)
  5. Se marca como completo el nodo a.
  6. 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[editar]

Orden de complejidad del algoritmo:

O(|V|2+|A|) = O(|V|2), sin utilizar cola de prioridad, :O((|A|+|V|) log |V|) = O(|A| log |V|) utilizando cola de prioridad (por ejemplo, un montículo de Fibonacci). 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 Sk. 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 Sk.

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

Entonces:

Teorema: El algoritmo de Dijkstra realiza O(n2) 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|: Numero de vértices
𝑻_𝒅𝒎: Complejidad de extraer mínimo

Pseudocódigo[editar]

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 uV[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 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[editar]

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.

Implementación en Java[editar]

 0 	/**
 1 	 * Realizar el algoritmo de Dijkstra sobre el grafo
 2 	 * @param origen nodo inicial
 3 	 * @param destino nodo destino
 4 	 * @return camino ArrayList con el camino a seguir.
 5 	 */
 6 	  public ArrayList<Integer> dijkstra(int origen, int destino) {
 7 		  ArrayList<Integer> camino= new ArrayList<Integer>();
 8 		  int distancia=Grafo.INFINITO;
 9 		  int nodo=origen;
10 		  boolean fin=true;
11 		  camino.add(nodo);
12 		  while(fin) {
13 			  if(this.floydC[nodo][destino]<distancia) {
14 			      /*El metodo siguiente(nodo, destino), nos devuelve
15 			      el siguiente nodo a visitar*/
16 				  nodo=this.siguiente(nodo, destino);
17 				  camino.add(nodo);
18 			  }
19 			  
20 			  if(nodo==destino) {
21 				  fin=false;
22 			  }
23 		  }
24 		  
25 		  return camino;
26 	  }

Otra versión en C++ del algoritmo de Dijkstra[editar]

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

struct nodo { /* Indica eL estado del nodo,la ruta y quien lo precede a dicho nodo */
	int predecesor; /* nodo previo */
	int longitud; /* longitud del origen a este nodo */
	bool etiqueta;	/*verdadero para un nodo permanente y falso para nodo tentativo*/
} nodo[MAX_NODOS];

void inicializacion(){
	for (p = &nodo[0]; p < &nodo[n]; p++) { /* estado de inicialización*/
	        p->predecesor = -1;
	        p->longitud = INFINITO;
	        p->etiqueta = false;
        }
}
void relajar(){
	for (int i = 0; i <n; i++){ /* este grafo tiene n nodos */		
	        if (dist[k][i] != 0 && nodo[i].etiqueta == false) { 
		        if (nodo[k].longitud + dist[k][i] < nodo[i].longitud) {
			        nodo[i].predecesor = k;
		                nodo[i].longitud = nodo[k].longitud + dist[k][i];
		        }
                }
        }
}
void extraer_minimo(){ 	/* Encuentra los nodo etiquetados tentativamente y determina el menor entre estos nodos tentativos. */ 
	k = 0; 
	minimo = INFINITO;
	for (i = 0; i < n; i++){
		if (nodo[i].etiqueta == false && nodo[i].longitud < minimo) {
			minimo = nodo[i].longitud;
			k = i;
		}
	}
}

void camino_corto(int s, int t, int camino[]) { 
	inicializacion();
	nodo[t].longitud = 0; nodo[t].etiqueta = true;
	k = t; /* k es el nodo de trabajo inicial */
	do{ /* ¿hay una ruta mejor desde k? */			
		relajar();
		extraer_minimo();
		nodo[k].etiqueta = true;
	} while (k != s);
	/* Copia la ruta en el arreglo de salida y procede a ir imprimiendolo. */
	i = 0; k = s;
	cout<< "La ruta es: ";
	do {
		cout<< k<< " ";
		camino[i] = k; 
		k = nodo[k].predecesor; 
		i++;
	} while (k >= 0);
	cout <<"La ruta minima es: "<<minimo<<endl ;
}
int main(){
    int nodo_final,nodo_inicial,arista;
    //solicita o ingresa directamente los valores de nodo_final,nodo_inicial
    //Llenar de 0 la matriz
    for (int i=0; i<n; i++){
	    for( int j=0; j<n; j++){
	        dist[i][j]=0;
	    }
    }	
    // Llenar la matriz dist[i][j]
    /*............................
    ............................*/
    //Por ultimo llamar a la función camino corto
       camino_corto(nodo_final,nodo_inicial,camino)
    return 0;
}

Véase también[editar]

Enlaces externos[editar]