Caminos mínimos desde un origen

Algoritmo de Dijkstra

• Supongamos un grafo G, con pesos positivos y un nodo origen v.

• El algoritmo trabaja con dos conjuntos de nodos:

– Escogidos: S. Nodos para los cuales se conoce ya el camino mínimo desde el origen.

– Candidatos: T. Nodos pendientes de calcular el camino mínimo, aunque conocemos los caminos mínimos desde el origen pasando por nodos de S.

• Camino especial: camino desde el origen hasta un nodo, que pasa sólo por nodos escogidos, S.

dijks

• Idea: En cada paso, coger el nodo de T con menor distancia al origen. Añadirlo a S.

• Recalcular los caminos mínimos de los demás candidatos, pudiendo pasar por el nodo escogido.

Esquema del Algoritmo de Dijkstra

• Inicialización: S= {1}, T= {2, ..., n}, caminos especiales mínimos = caminos directos.

• Repetir n-1 veces:

– Seleccionar el nodo v de T con el camino especial más corto.

– Proposición: el camino mínimo para este nodo v, coincide con su camino especial.

– Recalcular los caminos especiales para los nodos de T, pudiendo pasar por v.

Implementación del algoritmo de Dijkstra

• Suponemos que el origen es el nodo 1 (para esta descripción, pero el nodo inicial puede ser cualquier nodo vI).

• D: array [2..n] de reales. D[v] almacena el costo del camino especial mínimo para el nodo v.

• P: array [2..n] de enteros. P[v] almacena el último nodo en el camino especial mínimo de v.

• Inicialización: D[v]:= C[1, v], P[v]:= 1 (recordar que en esta descripción el vértice inicial es 1, pero puede ser cualquier vértice vI)

• Nodo seleccionado: nodo de T con mínimo D[v]

•          Actualización: para todos los w de T hacer
               si D[v] + C[v, w] < D[w] entonces
                               D[w]:= D[v] + C[v, w]
                               P[w]:= v
               finsi

dijks2

• Camino especial para w:

– Sin pasar por v: D[w]

– Pasando por v: D[v] + C[v,w]

– Nos quedamos con el menor.

• Si el menor es pasando por v entonces: P[w]= v.

• Camino especial para w:
1 → ... → P[P[P[w]]] → P[P[w]] → P[w] → w

Pseudocódigo del Algoritmo de Dijkstra

• Entrada:
C: array [1..n, 1..n] de real → Matriz de costes

• Salida:

D: array [2..n] de reales → Costos de caminos mínimos

P: array [2..n] de enteros → Nodos de paso

• Datos para cálculos intermedios:
S: array [2..n] de booleano → Nodos escogidos

• Inicialización: para v:= 2, ..., n hacer

D[v]:= C[1, v]

P[v]:= 1

S[v]:= FALSE

finpara

para i:= 1, ..., n-1 hacer

v:= vértice con D[v] mínimo y S[v]==FALSE ⇒ S[v]:= TRUE

para cada vértice w adyacente a v hacer

si (S[w]==FALSE) y (D[v]+C[v,w]<D[w]) entonces

D[w]:= D[v] + C[v, w]

P[w]:= v

finsi

finpara

Pseudocódigo del algoritmo recursivo para Imprimir el camino más corto

ImprimeCamino(v: integer)

inicia

si v<> 1 entonces (recordar que aquí se supone que el vértice inicial es 1, pero puede ser cualquier vértice vI)

ImprimeCamino(P[v]);

escribe(v);

termina;

Eficiencia del algoritmo de Dijkstra

• Con matrices de adyacencia:

– Inicialización: O(n)

– Ejecutar n-1 veces:

• Buscar el nodo con mínimo D[v] y S[v] = falso: O(n)

• Actualizar los valores de los candidatos: O(n)

– En total: O(n²)

• Con listas de adyacencia:

– Seguimos teniendo un O(n²)

– Podemos modificar la implementación y conseguir un O(a·log n). Será adecuada cuando a << n².

Consultar el siguiente Link:

https://elibro.bibliotecabuap.elogim.com/es/ereader/bibliotecasbuap/50117?page=495