Breve Explicacion: Algoritmo De Dijkstra

Algoritmo de Dijkstra
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos loscaminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor,pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Fig. 1 Representación del algoritmo de 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 lagrá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 y los algoritmos ávidos. 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).

Algo que podemos notar es que al obtener el camino más corto de un puntoa 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 unacantidad 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.
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 laprimera.

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