Algoritmia/Algoritmo de Dijkstra

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

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.

Ejemplo[editar]

El siguiente ejemplo se mostrara como se desarrollará con el fin de encontrar el camino más corto desde a hasta z:

Dijkstrapaso0.jpg

Leyenda:

  • Rojo: Aristas y vértices pertenecientes a la solución momentánea.
  • Azul: Aristas y vértices candidatos.

Paso 1[editar]

Dijkstrapaso1.jpg

Se escoge de los nodos adyacentes aquel que tiene una menor peso en la arista, en este caso, el nodo d. En d

  • Distancia:5

Paso 2[editar]

Dijkstrapaso2.jpg

Ahora, vemos que se añade un nuevo candidato, el vértice e, y el vértice c, pero esta vez a través del d. Pero el camino mínimo surge al añadir el vértice c.

Solución momentánea:

  • Camino: ADC
  • Distancia:9

Paso 3[editar]

Dijkstrapaso4.jpg

Solución momentánea:

  • Camino: ADCB
  • Distancia:11

Paso 4[editar]

Dijkstrapaso5.jpg

Como podemos comprobar, se han añadido un candidato nuevo, el vértice g, a través del vértice b. El mínimo camino hallado en todo el grafo hasta ahora es el siguiente:

Solución momentánea:

  • Camino: ADCBF
  • Distancia:15

Paso 5[editar]

Dijkstrapaso6.jpg

En este antepenúltimo paso, se añaden tres vértices candidatos, los vértices g, z y e. Este último ya estaba pero en esta ocasión aparece a través del vértice f. En este caso el camino mínimo, que cambia un poco con respecto al anterior, es:

Solución momentánea:

  • Camino: ADCBG
  • Distancia:17

Paso 6[editar]

Dijkstrapaso7.jpg

En el penúltimo paso, vuelve a aparecer otro candidato: el vértice e, pero esta vez a través del vértice f. De todas formas, el camino mínimo vuelve a cambiar para retomar el camino que venía siguiendo en los pasos anteriores:

Solución momentánea:

  • Camino: ADCBFE
  • Distancia:18

Paso 7[editar]

Dijkstrapaso8.jpg

Por fin, llegamos al último paso, en el que sólo se añade un candidato, el vértice z a través del vértice e. El camino mínimo y final obtenido es:

Solución Final:

  • Camino: ADCBFEZ
  • Distancia:23

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 		  
14 		      
15 			  if(this.floydC[nodo][destino]<distancia) {
16 			      /*El metodo siguiente(nodo, destino), nos devuelve
17 			      el siguiente nodo a visitar*/
18 				  nodo=this.siguiente(nodo, destino);
19 				  camino.add(nodo);
20 			  }
21 			  
22 			  if(nodo==destino) {
23 				  fin=false
24 			  }
25 		  }
26 		  
27 		  return camino;
28 	  }

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;
}