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.




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.




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).

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

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(V²). 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:

•  Si tenemos una gráfica sin pesos, el camino más corto es el camino que pasa por la menor cantidad de vértices intermedios, por lo que una búsqueda en amplitud es lo indicado (sección 9.4).
•  Si tenemos una gráfica dirigida y acíclica (DAG), podemos hacer un ordenamiento topológico para después utilizar programación dinámica.
•  Si la gráfica tiene pesos negativos, entonces utilizamos el algoritmo Bellman-Ford.
•  Si queremos saber la distancia mínima entre todos los pares de puntos en la gráfica, lo más conveniente es utilizar Floyd (siguiente tema).
•  Si la gráfica tiene ciclos negativos, entonces no podemos obtener el camino más corto, ya que nos podemos quedar dando vueltas en alguno de estos ciclos haciendo el costo mínimo cada vez menor.

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

Valladolid: