Algoritmo de Dijkstra

Ejecución del algoritmo de Dijkstra

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 vértices en un grafo dirigido y 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 costo 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).

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 v_i.
4. Si la distancia desde x hasta v_i guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta v_i; esta se sustituye con la segunda nombrada, esto es:
   si (D_i > D_a + d(a,v_i)) entonces D_i = D_a + d(a,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|²+|E|) = O(|V|²) sin utilizar cola de prioridad, O((|E|+|V|) log |V|) utilizando cola de prioridad (por ejemplo un montículo).

Podemos estimar la complejidad computacional del algoritmo de Dijkstra (en términos de sumas y comparaciones). El algoritmo realiza a lo más n-1 iteraciones, ya que en cada iteración se añade un vértice al conjunto distinguido. Para estimar el número total de operaciones basta estimar el número de operaciones que se llevan a cabo en cada iteración. Podemos identificar el vértice con la menor etiqueta entre los que no están en S_k realizando n-1 comparaciones o menos. Después hacemos una suma y una comparación para actualizar la etiqueta de cada uno de los vértices que no están en S_k. Por tanto, en cada iteración se realizan a lo sumo 2(n-1) operaciones, ya que no puede haber más de n-1 etiquetas por actualizar en cada iteración. Como no se realizan más de n-1 iteraciones, cada una de las cuales supone a lo más 2(n-1) operaciones, llegamos al siguiente teorema.

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)       
       for u ∈ V[G] do
           distancia[u] = INFINITO
           padre[u] = NULL
       distancia[s] = 0
       Encolar (cola, grafo)
       mientras cola no es vacía do          
           u = extraer_minimo(cola)
           for v ∈ adyacencia[u] do
               if distancia[v] > distancia[u] + peso (u, v) do
                   distancia[v] = distancia[u] + peso (u, v)
                   padre[v] = u

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
  int distancia[n] //Inicializamos el vector con distancias iniciales
  boleano visto[n] //vector de boleanos para controlar los vertices 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
     Sino
         distancia[w] = peso (s, w)
     fsi 
  fpara
  distancia[s] = 0
  visto[s] = cierto
  //n es el número de vertices que tiene el Grafo
  mientras (no_esten_vistos_todos) hacer 
     vertice = coger_el_minimo_del_vector distancia y que no este visto;
     visto[vertice] = cierto;
     para cada w ∈ sucesores (G, vertice) hacer
         si distancia[w]>distancia[vertice]+peso (vertice, w) entonces
            distancia[w] = distancia[vertice]+peso (vertice, w)
         fsi
     fpara
  fmientras
finfuncion

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

Implementación

C++

 
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int destino, origen, vertices = 0;
int *costos = NULL;
 
void dijkstra(int vertices, int origen, int destino, int *costos) {
    int i, v, cont = 0;
    int *ant, *tmp;
    int *z;                 /* vertices para los cuales se conoce el camino minimo */
    double min;
    double *dist = new double[vertices];  /* vector con los costos de dos caminos */
 
    /* aloca las lineas de la matriz */
    ant = new int[vertices];
    tmp = new int[vertices];
    z = new int[vertices];
   
    for (i = 0; i < vertices; i++) {
        if (costos[(origen - 1) * vertices + i] !=- 1) {
            ant[i] = origen - 1;
            dist[i] = costos[(origen-1)*vertices+i];
        }
        else {
            ant[i]= -1;
            dist[i] = HUGE_VAL;
        }
        z[i]=0;
    }
    z[origen-1] = 1;
    dist[origen-1] = 0;
 
    /* Bucle principal */
    do {
 
        /* Encontrando el vertice que debe entrar en z */
        min = HUGE_VAL;
        for (i=0;i<vertices;i++)
            if (!z[i])
                if (dist[i]>=0 && dist[i]<min) {
                    min=dist[i];v=i;
                }
 
        /* Calculando las distancias de los nodos vecinos de z */
        if (min != HUGE_VAL && v != destino - 1) {
            z[v] = 1;
            for (i = 0; i < vertices; i++)
                if (!z[i]) {
                    if (costos[v*vertices+i] != -1 && dist[v] + costos[v*vertices+i] < dist[i]) {
                        dist[i] = dist[v] + costos[v*vertices+i];
                        ant[i] =v;
                    }
                }
        }
 
    } while (v != destino - 1 && min != HUGE_VAL);
 
    /* Muestra el resultado de la búsqueda */
    cout << "\tDe " << origen << " para "<<destino<<" \t";
    if (min == HUGE_VAL) {
        cout <<"No Existe\n";
        cout <<"\tCoste: \t- \n";
    }
    else {
        i = destino;
        i = ant[i-1];
        while (i != -1) {
            //   printf("<-%d",i+1);
            tmp[cont] = i+1;
            cont++;
            i = ant[i];
        }
 
        for (i = cont; i > 0; i--) {
            cout<< tmp[i-1]<<" -> ";
        }
        cout << destino;
 
        cout <<"\n\tCoste: " << dist[destino-1] <<"\n";
    }
 
    delete (dist);
    delete (ant);
    delete (tmp);
    delete (z);
}
 
int menu(void) {
	int opcion;
    cout <<"         Implementacion del Algoritmo de Dijkstra\n";
    cout <<" Menu:\n";
    cout <<" >> 1. Crear el grafo\n >> 2. Determinar el menor camino del grafo\n >> 0. Salir del programa\n";
    cout <<endl;
	cout << " Opcion: ";
	cin>>opcion;
	while(opcion<0 || opcion>2){
		cout<<" Opcion Invalida. Digitela nuevamente: ";
		cin>>opcion;
	}
	return opcion;
}
 
void add(void) {
 
 
    do {
    	cout <<"\nIngrese el numero de vertices ( no minimo de 2 ): ";
        cin>>vertices;
    } while (vertices < 2 );
 
    if (!costos)
    	delete(costos);
 
    costos = new int[vertices * vertices];
 
 
    for (int i = 0; i <= vertices * vertices; i++)
        costos[i] = -1;
 
    cout <<" Nº Vertices = "<< vertices<<endl;
    cout <<"Ahora unamos los vertices:\n" ;
 
    bool sigo=true;
 
    int origen;
    int destino;
 
    while (sigo){
    	cout << " Escoja el primer vertice de la arista: " <<endl;
    	do{
    		cin >> origen;
 
    		if (origen>vertices){
    			cout << "  El numero del vertice debe ser menor de " << vertices<<endl;
    		}
    	}while(origen > vertices);
 
 
    	cout << " Escoja el segundo vertice de la arista: " <<endl;
    	do{
    		cin >> destino;
 
	 	if (destino>vertices){
	 		cout << " El numero de vertice debe ser menor de " << vertices<<endl;
	 	}
	 }while(destino> vertices);
 
	 int peso=0;
		cout <<" Peso: " <<endl;
	 cin>>peso;
 
	 costos[(origen-1) * vertices + destino - 1] = peso;
        costos[(destino-1) * vertices + origen - 1] = peso;
 
 
	 int seguir=1;
	 cout << "Desea anadir otra arista? (0 - NO, 1 - SI, por defecto 1): " ;
	 cin >>seguir;
	 sigo = (seguir==1);
    }
 
}
 
void buscar(void) {
    int i, j;
 
    cout <<" Lista de los Menores Caminos en Grafo Dado: \n";
 
    for (i = 1; i <= vertices; i++) {
        for (j = 1; j <= vertices; j++)
            dijkstra(vertices, i,j, costos);
        cout<<endl;
    }
 
    cout <<"<Presione ENTER para volver al menu principal. \n";
 
}
 
int main(int argc, char **argv) {
    int opcion;
 
    do { 
	opcion = menu();
	switch(opcion) {
		case 1:
			add();
			break;
		case 2:
			buscar();
			break;
	}
 
    } while (opcion!= 0);
	delete(costos);

    cout<<"\nHasta la proxima...\n\n";
    system("pause");
 
    return 0;
}

C++ mediante Heaps

Otra posible implementación del algoritmo de Dijkstra es mediante montículos binarios.

struct T_Heap{
       A monticulo;
       int num_elem;
};

void CrearHeap(T_Heap& heap){
     heap.num_elem= 0;
     for (int i=0;i<MAX_HEAP;i++){
         heap.monticulo[i]= NULL;
     }//for
}
void Intercambiar(T_Heap& heap, int i, int j){
     T_Lista aux;
     
     aux= heap.monticulo[i];
     heap.monticulo[i]= heap.monticulo[j];
     heap.monticulo[j]= aux;
}
void Meter(T_Heap& heap, const T_Lista& elem){
     int k;
     
     k= heap.num_elem;
     heap.monticulo[k]= elem;
     while(k != 0 || (heap.monticulo[k]->peso > heap.monticulo[((k-1)/ 2)]->peso){
         Intercambiar(heap,k,((k-1)/2));
         k= (k-1)/2;
     }//while
     heap.num_elem++;
}
void Sacar(T_Heap& heap, int& elem){
     int k;
     
     elem= heap.monticulo[0];
     heap.monticulo[0]= heap.monticulo[heap.num_elem-1];
     heap.monticulo[heap.num_elem-1]= NULL;
     heap.num_elem--;
     k= 0;
     while(k<heap.num_elem && (heap.monticulo[k]->peso < heap.monticulo[2*k+1]->peso ||
           heap.monticulo[k]->peso < heap.monticulo[2*k+2]->peso)){
       if (heap.monticulo[k] < heap.monticulo[2*k+1]){
          Intercambiar(heap,k,2*k+1);
          k= 2*k+1;
       }else{
          Intercambiar(heap,k,2*k+2);
          k= 2*k+2;
       }//if
     }//while
}
bool HeapLleno(const T_Heap& heap){
     return(heap.num_elem== MAX_HEAP);
}
bool HeapVacio(const T_Heap& heap){
     return(heap.num_elem== 0);
}
void DestruirHeap(T_Heap& heap){
     for (int i=0;i<MAX_HEAP;i++){
         heap.monticulo[i]= NULL;
     }//for
     heap.num_elem= 0;
}

Esta es una implementación del algoritmo de Dijkstra mediante montículos binarios, que es capaz de dar los mejores resultados para que el algoritmo de Johnson sea más eficiente. La implementación del algoritmo devuelve un array de elementos precedentes y otro de distancias, mediante el primero se puede seguir el camino de menor coste desde el nodo pasado como argumento a cualquier otro nodo del grafo, y si paralelamente vamos sumando las distancias del otro array, obtenemos el coste total de dichos caminos mínimos.

void Dijkstra(const T_Grafo& grafo, int origen, T_Vector& distancias, T_Vector& previos)
{
     T_Vector marcados;
     T_Heap colap;
     T_Lista aux;
     
     InicializarVector(distancias); // inicializa los elementos a -1
     InicializarVector(previos);
     InicializarVector(marcados);
     distancias[origen]= 0;
     marcados[origen]= 0;
     CrearHeap(colap);
     MeterAdyacentes(colap, grafo, origen, marcados);
     while (!HeapVacio(colap){
           aux = Sacar(colap);
           marcados[aux->origen]= 0;
           MeterAdyacentes(colap, grafo, aux->origen, marcados);
           while (aux != NULL){
               if (distancias[aux->destino] > (distancias[aux->origen] + aux->peso)){
                   distancias[aux->destino]= distancias[aux->origen] + aux->peso;
                   padre[aux->destino] = aux->origen;
               }//if
               aux= aux->sig;
           }//while
     }//while
}

Enlaces externos

• Wikimedia Commons alberga una galería multimedia sobre Algoritmo de Dijkstra.
• Analiza Algoritmo de Dijkstra en JavaScript
• Presentación 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
• Arquimedex.com Tutorial del Algoritmo de Dijkstra
• Video Tutorial en VideoPractico.com de Dijkstra
• giswiki.net Algoritmo de Dijkstra en lenguajes como PHP, Actionscript y otros