10.4. Camino más corto: Dijkstra.

Uno de los problemas más comunes al utilizar gráficas es encontrar el camino entre dos puntos de tal forma que el peso total de las aristas visitadas sea mínimo. Un ejemplo clásico es cuando la gráfica representa una ciudad donde las aristas son las calles (pueden ser dirigidas o no), los vértices las intersecciones, y el peso de las aristas el tiempo que toma recorrer la calle, nos puede interesar encontrar la forma para llegar de un punto a otro de tal forma que el tiempo sea mínimo.

Para encontrar el camino más corto utilizaremos el principio de que para que un camino sea óptimo, todos los caminos que contiene también deben ser óptimos. Dos técnicas de programación que aprovechan esta propiedad son programación dinámica (capítulo 8) y los algoritmos ávidos (sección 11.7). En este caso, podemos encontrar la distancia más corta de forma ávida. Otra propiedad importante es que el camino más corto no contiene ciclos (es un árbol).

El algoritmo de Dijkstra utiliza las propiedades anteriores y funciona de la siguiente forma. Primero marcamos todos los vértices como no utilizados. Entre todos los vértices, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).

Algo que podemos notar es que al obtener el camino más corto de un punto a otro, también estamos obteniendo el camino más corto del primero a todos los vértices intermedios que tenemos que visitar. Por esto, podemos encontrar el camino más corto entre uno punto y todos los demás de forma casi igual que como obtenemos la distancia más corta de un punto a otro.

El algoritmo de Dijkstra sólo funciona con pesos (distancias) positivos. Con negativos, si agregamos una cantidad fija a cada arista para hacerlas todas positivas para después utilizar Dijkstra, no obtiene el camino más corto de la gráfica original. Esto se debe a que a las trayectorias que contengan muchas aristas les estaremos agregando más pesos que a las que tengan pocas.


Problema ejemplo


Subterráneo

Problema
Imagina que te encuentras en una gran ciudad, y quieres ir del punto a al b. Para ello, puede moverte a pie o por metro. Ir en metro es más rápido pero tienes que ir a las estaciones. Para ahorrar tiempo, decides escribir un programa que encuentre la ruta más rápida.

Entrada
La entrada comienza con dos números de punto flotante en la primera línea. El primero de ellos es la velocidad de caminar, y el segundo la de trasladarse en metro. La segunda velocidad siempre es mayor a la primera.

Después viene la descripción del metro. Empieza con un entero n en la primera línea, que es la cantidad de estaciones del metro. Puedes asumir que n no será mayor a 200. Las siguientes n líneas tendrán dos números de punto flotante cada una (la i-ésima línea contiene las coordenadas de la i-ésima estación). Después sigue la descripción de las conexiones entre estaciones. La lista de conexiones termina con un par de ceros. Asumiremos que todas las conexiones son rectas, así que el tiempo que se necesita para ir de una estación a otra es igual a la distancia entre estaciones dividida por la velocidad del metro. Entrar y salir del metro, o cambiar de metro sólo es posible en las estaciones, y se considera que estas operaciones son instantáneas.

Por último, se dan las coordenadas de los puntos a y b, una coordenada por línea.

Salida
La primera línea de la salida deberá contener el tiempo mínimo que se necesita para ir del punto a al b. Este resultado debe tener una precisión de 10-6. La segunda línea describe el uso del metro para desplazarse. Empieza con la cantidad de estaciones visitadas, seguida por la lista de las estaciones en el orden en que se visitaron.

Solución: Todos los puntos en el plano los podemos ver como vértices de la gráfica, a la recta que los une como la arista y a la longitud de esta línea como el peso de la arista. Lo que queremos obtener es la distancia mínima entre dos puntos dados, lo cual podemos obtener con Dijkstra.


Código


En las primeras seis líneas de código tenemos la declaración de variables. Los enteros i y j los utilizamos en los ciclos, n para leer la cantidad de estaciones, mientras que c1 y c2 para leer las conexiones entre estaciones. En los flotantes vf y vu guardamos las velocidades de viajar a pie y en metro. El arreglo m contiene a la matriz de adyacencia, en x e y leemos las coordenadas de las estaciones y de los puntos donde empezamos y terminamos, y en v anotamos las estaciones que tenemos que visitar.

En seguida tenemos el procedimiento Dijkstra (líneas 8 a 33), que es donde encontramos el tiempo mínimo para llegar y la trayectoria a seguir. Tenemos como parámetros s, que el vértice en el que comenzamos, y a n, que es la cantidad de vértices. Empezamos inicializando los vértices como no utilizados y que no visitamos algún vértice anterior para llegar (líneas 13 y 14). Entre las líneas 16 y 32 vamos utilizando un vértice a la vez para mejorar los tiempos que ya tenemos. Entre las líneas 18 y 24 buscamos el vértice más cercano que no hayamos utilizado, guardamos su posición y lo marcamos como usado. Después vemos si podemos mejorar los tiempos para llegar a otros vértices tomando al que obtuvimos como punto intermedio (líneas 25 a 31). En caso de que sea posible mejorar, actualizamos el tiempo (líneas 28 y 29), y guardamos el vértice con el que llegamos. En las líneas 28 y 29 actualizamos dos tiempos, ya que las aristas no tienen dirección.

En la función trayectoria (líneas 35 a 41) imprimimos las estaciones a recorrer para llegar en el tiempo mínimo. Empezamos por la última estación y revisamos cual punto visitamos para llegar a esta. Luego vamos al penúltimo punto y a su vez examinamos cual punto fue el anterior a este. Repetimos esto hasta llegar a la primera estación que visitamos, y contamos cada repetición  para saber cuantas estaciones visitamos. Al llegar al la primera, regresamos imprimiendo las estaciones, con lo que quedan ordenadas de primera a última.

La parte principal del código la tenemos entre las líneas 43 y 65. Empezamos inicializando la matriz de adyacencia a ceros (línea 44). Continuamos leyendo las velocidades a pie y en metro (línea 45), para después leer las coordenadas de cada estación (líneas 46 a 48). De la línea 49 a la 55, leemos cuales estaciones están conectadas, calculamos el tiempo en que llegamos de una a otra, y guardamos ese valor en m. Después leemos las coordenadas de inicio y final (líneas 56 y 57). Proseguimos calculando el tiempo que nos toma llegar de un lugar a otro a pie (líneas 58 a 61), excepto para las estaciones que están conectadas. Una vez hecho esto, obtenemos la distancia más corta utilizando Dijkstra (líneas 62), y la imprimimos junto con la trayectoria (líneas 63 y 64).


Caso ejemplo

Entrada: 1 100
4
0 0
1 0
9 0
9 9
1 2
1 3
2 4
0 0
10 10
10 0
Desarrollo: vis[]:    TRUE  FALSE  FALSE  FALSE  FALSE  FALSE
m[s,]:   0.000 14.142 13.454 10.050  1.414 10.000
v[]  :       0      0      0      0      0      0

p: 4; min: 1.414
vis[]:    TRUE  FALSE  FALSE  FALSE   TRUE  FALSE
m[s,]:   0.000 14.142  1.535 10.050  1.414 10.000
v[]  :       0      0      4      0      0      0

p: 2; min: 1.535
vis[]:    TRUE  FALSE   TRUE  FALSE   TRUE  FALSE
m[s,]:   0.000  1.545  1.535  9.535  1.414 10.000
v[]  :       0      2      4      2      0      0

p: 1; min: 1.545
vis[]:    TRUE   TRUE   TRUE  FALSE   TRUE  FALSE
m[s,]:   0.000  1.545  1.535  1.635  1.414 10.000
v[]  :       0      2      4      1      0      0

p: 3; min: 1.635
vis[]:    TRUE   TRUE   TRUE   TRUE   TRUE  FALSE
m[s,]:   0.000  1.545  1.535  1.635  1.414  2.635
v[]  :       0      2      4      1      0      3

p: 5; min: 2.635
vis[]:    TRUE   TRUE   TRUE   TRUE   TRUE   TRUE
m[s,]:   0.000  1.545  1.535  1.635  1.414  2.635
v[]  :       0      2      4      1      0      3
Salida: 2.6346295
4 4 2 1 3


Información Adicional

El tiempo de ejecución lo podemos calcular rápidamente considerando el ciclo de la línea 16 y los ciclos de las líneas 19 y 25, como los últimos dos están anidados dentro del primero y en los tres casos recorremos todas los vértices, por lo que tenemos un tiempo de O(V2). Podemos mejorar este tiempo utilizando montículos (sección 3.4). El siguiente vértice que está más cercano (línea 19) lo podemos obtener en la raíz del montículo, quitar este vértice y actualizar el montículo lo hacemos en O(lgV), y los vértices que actualizamos en la línea 25 son los que están todavía en el montículo y que podemos actualizar en O(lgV). También podemos utilizar montículos de Fibonacci, que son más eficientes para este problema en particular.

Otra aplicación de Dijkstra es que con ligeros cambios, podemos obtener las aristas mini-max y maxi-min. Teniendo un par de vértices, queremos encontrar la forma de llegar de uno a otro de tal manera que el peso de las aristas que recorramos sea el mínimo y, una vez hecho esto, queremos saber cual de estas aristas fue la más pesada. Esto es para mini-max, para maxi-min buscamos la arista más liviana en el camino con aristas de peso mayor. Estas estrategias se utilizan principalmente en la teoría de juegos para tomar decisiones que nos lleven a minimizar la pérdida máxima posible (mini-max), o a maximizar la mínima ganancia (maxi-min).


Estas seis líneas corresponderían a las líneas 25 a 31 del programa anterior. Las funciones max y min devuelven el mayor y menor de dos números, respectivamente. Con este cambio estamos calculando el maxi-min, para obtener el mini-max sólo debemos cambiar el orden de las operaciones.

Generalmente para resolver un problema de camino más corto entre dos puntos utilizamos Dijkstra. Sin embargo, existen ocasiones especiales donde es más conveniente utilizar otros algoritmos:

Código en C



Tiempo de ejecución

Lenguaje Fecha Tiempos [s] Memoria [Kb]
Ejecución Mejor Mediana Peor
Pascal 30-May-2006 0.015 0.001 0.031 0.953 550
C 30-May-2006 0.015 466


Otros problemas

Valladolid:





© Pier Paolo Guillen Hernandez
World of πer