Algoritmo de Dijkstra

Algoritmo de Dijkstra 260px Concepto: Algorítmo para buscar el camino de menor costo entre dos vértices dados:

En múltiples aplicaciones donde se aplican los grafos, es necesario conocer el camino de menor costo entre dos vértices dados:

• Distribución de productos a una red de establecimientos comerciales.
• Distribución de correos postales.
• Sea G = (V, A) un grafo dirigido ponderado.

El problema del camino más corto de un vértice a otro consiste en determinar el camino de menor costo, desde un vértice u a otro vértice v. El costo de un camino es la suma de los costos (pesos) de los arcos que lo conforman.

Características del algoritmo

• Es un algoritmo greddy.
• Trabaja por etapas, y toma en cada etapa la mejor solución sin considerar consecuencias futuras.
• El óptimo encontrado en una etapa puede modificarse posteriormente si surge una solución mejor.

Pasos del algoritmo

Algoritmo 24.1: Algoritmo de Dijkstra. Inicialización.

• Sea V un conjunto de vértices de un grafo.
• Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v.
• Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo.
• Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v.
• Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido.
• Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices.

 Paso 1. S ← {vinicial} //Inicialmente S contendrá el vértice //origen
 Paso 2. Para cada v∈V, v ≠ vinicial, hacer
    2.1. D[v] ← C[vinicial, v] //Inicialmente el costo del //camino mínimo de vinicial a v es lo contenido en //la matriz de costos
    2.2. P[v] ← vinicial //Inicialmente, el //predecesor de v en el camino mínimo construido //hasta el momento es vinicial
 Paso 3. Mientras (V – S ≠ ∅) hacer //Mientras existan vértices para //los cuales no se ha determinado el //camino mínimo
    3.1. Elegir un vértice w∈(V-S) tal que D[w] sea el mínimo.
    3.2. S ← S ∪ {w} //Se agrega w al conjunto S, pues ya se //tiene el camino mínimo hacia w 
    3.3. Para cada v∈(V-S) hacer
    3.3.1. D[v] ← min(D[v],D[w]+C[w,v]) //Se escoge, entre //el camino mínimo hacia v que se tiene //hasta el momento, y el camino hacia v //pasando por w mediante su camino mínimo, //el de menor costo.
    3.3.2. Si min(D[v],D[w]+C[w,v]) = D[w]+C[w,v] entonces P[v] ← w //Si se escoge ir por w entonces //el predecesor de v por el momento es w
 Paso 4. Fin 

Ejecución de algoritmo

• Paso 1: Inicialización

• Paso 2: Elegir un vértice w ∈ V - {A} tal que D[w] sea mínimo, y agregar w al conjunto solución S

• Paso 3: cada v ∈ {C, D, E} hacer D[v] ← min( D[v], D[w]+C[w, v] )

• Paso 4: Elegir un vértice w ∈ V - {A, B} tal que D[w] sea mínimo, y agregar w al conjunto solución S.

• Paso 5: Para cada v ∈ {C, E} hacer D[v] ← min( D[v], D[w]+C[w, v]

Archivo:Algo09.JPG

• Paso 6: Elegir un vértice w ∈ V - {A, B, D} tal que D[w] sea mínimo, y agregar w al conjunto solución S.

• Paso 7: Para cada v ∈ { E} hacer D[v] ← min( D[v], D[w]+C[w, v]

• Paso 8: Elegir un vértice w ∈ V - {A, B, D, C} tal que D[w] sea mínimo, y agregar w al conjunto solución S.

Final del Proceso de Ejecución =

Luego del paso 8 tenemos la siguiente situación:

• El conjunto de vértices V = {A, B, C, D, E}
• El conjunto de vértices para los que ya se determinó el camino mínimo S = {A, B, D, C, E}

Por lo que como V-S=Ø se termina el algoritmo, pues para cada nodo del grafo se ha determinado cuál es su camino mínimo. Como resultado de la ejecución del algoritmo tenemos:

    D[B] D[C] D[D] D[E] 	 P[B] P[C] P[D] P[E]
     10   50   30   60 	           A    D    A    C 

Al finalizar la ejecución del algoritmo Dijkstra, en el arreglo D quedan almacenados los costos de los caminos mínimos que parten del vértice origen al resto de los vértices. Por tanto, en nuestro ejemplo, el camino mínimo de A hacia B tiene costo 10, el camino mínimo de A hacia C tiene costo 50, el camino mínimo de A hacia D tiene costo 30 y el camino mínimo de A hacia E tiene costo 60.

Veamos cómo se pueden obtener los caminos mínimos a partir del arreglo de predecesores. Los caminos se reconstruyen partiendo del vértice destino hasta llegar al vértice origen.

CaminoMínimo (A, B) = AB ya que P[B]=A
CaminoMínimo (A, C) = ADC ya que P[C]=D y P[D]=A
CaminoMínimo (A, D) = AD ya que P[D]=A
CaminoMínimo (A, E) = ADCE ya que P[E]=C, P[C]=D y P[D]=A

Finalmente, el camino mínimo que incluye todos los vértices del grafo es ADCE.

Enlaces externos

• 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
• Video Tutorial en VideoPractico.com de Dijkstra
• giswiki.net Algoritmo de Dijkstra en lenguajes como PHP, Actionscript y otros