Instinto Lógico

Recuerda que nadie debe pensar por tí.

Dijkstra y el camino más corto

dijkstra_edgarEdsger Dijkstra (1930 -2002 ) es uno de los padres de la informática al que poca gente ajena a la informática conoce. Éste físico teórico realizó contribuciones fundamentales al campo de la informática actual están los semáforos, el algoritmo del banquero o la notación polaca inversa.

Todas las contribuciones mencionadas anteriormente han supuesto un avance significativo en el desarrollo informático, pero en esta entrada nos vamos a centrar en una de las contribuciones de Dijkstra que más se ha popularizado en los últimos tiempos gracias al uso de los GPS. Se trata del algoritmo que lleva su nombre: “El algoritmo de Dijkstra”.

El algoritmo de Dijkstra se aplica sobre un grafo ponderado y calcula la distancia desde un vértice inicial al resto de vértices del grafo. Los GPS tratan el mapa de carreteras como un grafo ponderado (cuyos pesos son o bien la distancia o el tiempo) y utilizan este algoritmo para calcular el camino más corto entre dos puntos.

Formulación del algoritmo de Dijkstra

Como se ha dicho anteriormente, el algoritmo de Dijkstra calcula la distancia desde un vértice inicial s al resto de vértices del grafo. En cada paso etiquetaremos los vértices del grafo de la siguiente forma: (dist(u),v), dónde dist(u) es la distancia acumulada desde el vértice s al u y v es el vértice predecesor de u en el camino más corto de s a u.

Para realizar el algoritmo de Dijkstra utilizaremos las siguientes estructuras:

  • Un grafo ponderado (G,w) representado mediante una lista de adyacencias. G representa el conjunto de vértices y w (u, v) el peso del arco (u,v)
  • Un conjunto U de los vértices que se han visitado, en el orden en el que se ha hecho.
  • Una tabla de distancias, dist(・), indexada por los vértices de G, que registra la distancia del vértice inicial a los vértices que se van visitando.
  • Al final, la tabla dist(・) registra la distancia desde el vértice inicial al resto de los vértices.

Cuando es posible visitar más de un vértice, se elige el vértice con índice mínimo en la ordenación de vértices disponibles (Se podría tomar cualquier otra forma de selección arbitraria).

Entrada : (G,w) de orden n y un vértice inicial s.

Salida : La distancia, dist(・), de s al resto de los vértices.

algoritmo Dijkstra(G,s)

     inicio

U ← ∅

          para v ∈ V\{s}

dist(v) ← ∞

Se etiqueta v con (dist(v),s)

          finpara

dist(s) ← 0

Se etiqueta s con (dist(s),s)

    para i ← 0 hasta n – 1

ui vértice que logra lo min{dist(v) | v ∈ V – U}

U ← U ∪ {ui}

     para v ∈ V – U adyacente a ui

          si dist(ui) + w(ui,v) < dist(v)

               entonces dist(v) ← dist(ui) + w(ui,v)

Se etiqueta v con (dist(v),ui)

          finsi

     finpara

finpara

retorno (dist)

fin

 

Al finalizar, para cada vértice del grafo tenemos que dist(v) es la distancia mínima entre s y v y podemos obtener un camino de longitud mínima siguiendo los predecesores de cada uno de los vértices.

Simulación del algoritmo de Dijkstra

Consideramos el grafo definido sobre un mapa que representa las distancias entre varias poblaciones de la comarca de las cinco villas en Aragón:

Vamos a utilizar el algoritmo de Dijkstra para encontrar la distancia más corta desde El Frago y el resto de poblaciones.

Por simplificar la notación utilizaremos la siguente nomenclatura para cada una de las poblaciones.

Mapa Dijkstra El Frago –>EFBiel –> B

Luna –> L

Erla –>E

Ejea de los Caballeros–> EC

Castejón de Valdejasa –>CV

Rivas –> R

Farasdués –> F

Asín –>A

Orés –>O

Luesa –>Lu

Sadaba—->S

Uncastillo –>U

Castidiscar –> C

Sierra de Luna –>SL

Sos del Rey Católico –>SOS

Representamos el grafo resultante:

GrafoDijkstra

Utilizaremos la siguiente tabla para representar el algoritmo de Dijkstra

EF
A
B
CV
C
EC
E
F
P
Lu
L
O
R
S
SL
SOS
U
U
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
dist
(0, EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)
(∞ ,EF)

La tabla anterior representa el estado inicial del algoritmo de Dijkstra. Se va a obtener la distancia más corta de EF al resto de poblaciones. Inicialmente, se llega a de EF a EF con distancia 0 y al resto de nodos distancia infinita. El conjunto U representa los vértices que se han visitado.

Cada vez que se visita un vértice, se establecen los pesos de sus vecinos según el algoritmo:

si dist(ui) + w(ui,v) < dist(v)

entonces dist(v) ← dist(ui) + w(ui,v)

Así pues:

i=0. El vértice de peso mínimo es EF, lo marcamos como visitado y podemos etiquetar a sus vecinos, En este caso Biel (B) y Luna (L)

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
dist( (0, EF) (∞ ,EF) (16 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (14 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF)

i=1 El buscamos entre los vértices no visitados (marcados con 0 en el conjunto U) el que tiene peso mínimo. En este caso tomamos el vértice L. Y establecemos los pesos con sus vecinos tal y como se ha indicado anteriormente y establecemos el nodo predecesor. En lo que sigue se indica en negrita las modificaciones en cada iteración.

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
dist( (0, EF) (∞ ,EF) (16 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (22 ,L) (∞ ,EF) (∞ ,EF) (14 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF)

i=2. Repetimos la misma operación: buscamos entre los vértices no visitados el que tiene peso mínimo y establecemos los nuevos pesos y el nodo predecesor.

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
dist( (0, EF) (∞ ,EF) (16 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (22 ,L) (∞ ,EF) (31 ,B) (14 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF)

Iterando el proceso se tiene:

i=3

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0
dist( (0, EF) (∞ ,EF) (16 ,EF) (∞ ,EF) (∞ ,EF) (39 ,E) (22 ,L) (∞ ,EF) (31 ,B) (14 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (34 ,E) (∞ ,EF) (∞ ,EF)

i=4

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0
dist( (0, EF) (46,Lu) (16 ,EF) (∞ ,EF) (∞ ,EF) (39 ,E) (22 ,L) (∞ ,EF) (31 ,B) (14 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (34 ,E) (∞ ,EF) (49 ,Lu)

i=5

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (∞ ,EF) (31 ,B) (14 ,EF) (∞ ,EF) (∞ ,EF) (∞ ,EF) (34 ,E) (∞ ,EF) (49 ,Lu)

i=6

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (∞ ,EF) (31 ,B) (14 ,EF) (∞ ,EF) (47 ,EC) (69 ,EC) (34 ,E) (∞ ,EF) (49 ,Lu)

i=7

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (∞ ,EF) (49 ,Lu)

i=8

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (∞ ,EF) (49 ,Lu)

i=9

Notar que en esta iteración, marcamos el vértice R pero no hay ninguna modificación en los pesos ni en lo predecesores ya que para llegar a su vecino F se el peso acumulado sería 47+9=56 que es mayor que el peso acumulado que ya tenemos en F.

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 0 0 1 1 0 1 1 0 1 0 1 0 0
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (∞ ,EF) (49 ,Lu)

i=10

Nota: En esta iteración podemos elegir, por peso mínimo, los vértices CV ó U. Por convenio elegimos el primero de ellos. E igual que pasaba en la iteración anterior no hay modificaciones en los pesos ni en los predecesores.

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (∞ ,EF) (49 ,Lu)

i=11

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 1 0 1 1 0 1 1 0 1 0 1 0 1
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (74 ,U) (49 ,Lu)

i=12

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (74 ,U) (49 ,Lu)

i=13

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (∞ ,EF) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (74 ,U) (49 ,Lu)

i=14

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (86 ,S) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (74 ,U) (49 ,Lu)

i=15

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (85 ,SOS) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (74 ,U) (49 ,Lu)

i=16

EF A B CV C EC E F Lu L O R S SL SOS U
U 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
dist( (0, EF) (46,Lu) (16 ,EF) (49 ,EF) (85 ,SOS) (39 ,E) (22 ,L) (52 ,A) (31 ,B) (14 ,EF) (57 ,A) (47 ,EC) (69 ,EC) (34 ,E) (74 ,U) (49 ,Lu)

Con la útima tabla tenemos las distancias más cortas de El Frago (EF) al resto de poblaciones y a partir de sus predecesores podremos construir la ruta completa.

Así pues por ejemplo, para ir del El Frago (EF) a Casdtilistar (C) tendremos 85 Km y la ruta la realizaremos a partir de los predecesores de C.

d(EF, C) = 85

La ruta en orden inverso observando los predecesores

C –> SOS –>U –>Lu –>B –>EF

De esta forma, tenemos que el camino más corto para ir de El Frago a Castiliscar es:

El Frago – Biel – Luesia – Uncastillo –SOS del Rey Católico – Castiliscar

Hay que tener en cuenta que en nuestro caso sólo hemos tenido en cuenta el kilometraje de las carreteras y no el tiempo invertido. Sería equivalente introducir como peso el tiempo estimado y con ello podríamos calcular la ruta más rápida.

Be Sociable, Share!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Instinto Lógico © 2014 Frontier Theme