Algoritmo Dijkstra
Algoritmo Dijkstra
Algoritmo Dijkstra
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]
�ndice
1 Algoritmo
2 Complejidad
3 Pseudoc�digo
4 Otra versi�n en pseudoc�digo sin cola de prioridad
5 Implementaci�n en Java
6 Otra versi�n en C++ del algoritmo de Dijkstra
7 V�ase tambi�n
8 Enlaces externos
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 vi.
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, entonces se
actualiza el vector con esta distancia tentativa. Es decir, si dt(vi) < Dvi ? Dvi =
dt(vi)
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|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:
Entonces:
En general:
Implementaci�n en Java
/**
* Realizar el algoritmo de Dijkstra sobre el grafo
* @param origen nodo inicial
* @param destino nodo destino
* @return camino ArrayList con el camino a seguir.
*/
public ArrayList<Integer> dijkstra(int origen, int destino) {
ArrayList<Integer> camino= new ArrayList<Integer>();
int distancia=Grafo.INFINITO;
int nodo=origen;
boolean fin=true;
camino.add(nodo);
while(fin) {
if(this.floydC[nodo][destino]<distancia) {
/*El metodo siguiente(nodo, destino), nos devuelve
el siguiente nodo a visitar*/
nodo=this.siguiente(nodo, destino);
camino.add(nodo);
}
if(nodo==destino) {
fin=false;
}
}
return camino;
}
Otra versi�n en C++ del algoritmo de Dijkstra
//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;
}
}
}