[AUDIO_EN_BLANCO] En este anexo, explicaremos cómo resolver los problemas de asignación a redes sin congestión. Para ello, ocuparemos el conocido Algoritmo de Dijkstra, que nos permite encontrar rutas mínimas en grafos. La pregunta que queremos encontrar, cuando no hay congestión es, ¿cuál es el camino más corto para ir desde un origen a un destino? Veremos un algoritmo muy eficiente para encontrar rutas mínimas, que está implementado con algunas modificaciones, para hacerlo más rápido, en la mayoría de los paquetes que buscan rutas mínimas y que ustedes, probablemente, han utilizado más de alguna vez. Este es el algoritmo de Dijkstra. El algoritmo de Dijkstra busca rutas mínimas en un grafo, a partir de un nodo fuente, que nosotros definimos arbitrariamente, a todos los restantes arcos de la red. Un requisito para utilizar este algoritmo es que todos los arcos tengan costos no negativos, lo que es bastante común en redes de transporte si pensamos en costos o tiempos de viaje, estos siempre son negativos. Es importante notar que no funciona en arcos con costos negativos. Por lo tanto, tenemos que buscar escribir nuestra red con arcos siempre no negativos para utilizarla. ¿Qué información necesita y guarda el algoritmo de Dijkstra? Necesita saber a qué distancia está un nodo a otro, por dónde llego a ese nodo y esa es la mínima distancia posible. Y por lo tanto, cada nodo se maneja con tres etiquetas. Hay una etiqueta que dice cuál es la distancia acumulada entre el nodo fuente y el nodo j. Hay otra etiqueta que me dice cuál es el nodo predecesor. Y hay otra en que me dice cuál es el estado del nodo j. Si está abierto todavía podemos asegurar que la distancia que tenemos encontrada es la mínima, y si está cerrado puedo asegurar que la distancia que encontré es la mínima para llegar desde el nodo fuente a ese nodo destino. Entonces, ¿qué pasos necesitamos seguir para encontrar las rutas mínimas desde un nodo fuente a todos los demás? Primero, definir cuál es el nodo fuente. Después, viene una etapa de inicialización en que para cada nodo distinto al fuente decimos que, la distancia acumulada es infinita y que el predecesor es sí mismo, por lo tanto no tenemos un camino para llegar a ese nodo y, por lo tanto, están todos abiertos. Después, tenemos una etapa de actualización de distancia, en que para todos los nodos adyacentes al último que fue cerrado y en el primer paso del nodo fuente, vamos a calcular cuál es la distancia de llegar a ese nodo, a partir del último que cerramos o la distancia que tenía. Y en caso de que hayamos encontrado un mejor camino, vamos a actualizar la etiqueta de distancia y la etiqueta de predecesor. Luego que ya actualizamos todas las distancias, elegimos el nodo con menor etiqueta de distancia y ese nodo lo vamos a cerrar. En cada iteración vamos a ir cerrando un nodo y vamos a ir, nuevamente, actualizando los demás. El algoritmo termina, el criterio de parada, va a ser cuando todas las etiquetas estén cerradas y, como en cada iteración cerramos un nodo, esto va a requerir el número de nodos como iteraciones para llegar al resultado. Veamos este ejemplo, yo lo voy a desarrollar acá en la transparencia pero, ustedes pueden ver cómo manejaría estos mismos valores un computador. Para denotar un nodo cerrado, lo que yo voy a hacer es al nodo que está así, cuando lo cierre le voy a poner un doble círculo. Y voy a poner sobre cada nodo una etiqueta, que va a ser un par, distancia, predecesor. Distancia, predecesor. ¿Okey? Entonces, vamos a buscar la ruta mínima desde el nodo 1 a todos los demás. El nodo 1, lo voy a cerrar, va a tener distancia 0. Y el predecesor es él mismo. Y todos los demás nodos, les voy a crear una etiqueta, igual a infinito con predecesor el mismo nodo, 3. Este va a ser infinito, 5. Este va a ser infinito, 4. Este va a ser infinito, 2. Con eso ya inicializamos el algoritmo. El siguiente paso va a ser actualizar distancias. Y para todos los nodos, que estén conectados directamente con el último cerrado, en este caso el nodo fuente, voy a comparar la distancia de ir directamente desde este nodo a él. Para el nodo 2, comparo la distancia de 0 más 4, menor que infinito. Y por lo tanto, lo que voy a hacer es actualizar esta etiqueta, y voy a decir que la nueva etiqueta es igual a 4 y el predecesor es 1. Para el nodo 3, voy a actualizar. Voy a decir que la nueva etiqueta es 1 y el predecesor es 1. Para el nodo 4, no hay camino. Y para el nodo 5, también actualizo y mi nueva etiqueta es 2, predecesor 1. Siguiente paso, veo qué nodo cerrar y que tenga etiqueta de distancia más pequeña. El nodo 2 tiene etiqueta 4, el nodo 3 tiene etiqueta 1, este infinito y este 2. Por lo tanto, cierro el nodo 3. Lo voy a cerrar. Y entonces, yo en este momento sé que este arco, el arco 1;3 va a ser parte del árbol de rutas mínimas. Va a ser un arco que vamos a ocupar para llegar, mínimamente, a 3 al menos y, tal vez, desde 3 a otros lados. Siguiente paso, va a ser actualizar distancias a los nodos adyacentes al nodo 3. Veo si puedo disminuir la etiqueta de distancia del nodo 2, a partir del nodo 3. Y 1 más 2 es 3, es menor que la etiqueta que tenía acá. Por lo tanto, voy a actualizar esta etiqueta, y va a ser ahora 3 y el predecesor va a ser el nodo 3. Al nodo 4, que tenía de etiqueta infinito, ahora yo puedo llegar con 4, predecesor 3. Y al nodo 5, 1 más 3, es mayor que 2 y, por lo tanto, no actualizo esa etiqueta de distancia. Con eso hemos terminado la etapa de actualización y nos preguntamos si podemos cerrar alguno de los nodos, si vamos a cerrar alguno de los nodos que está abierto. Voy a mirar la etiqueta del nodo 2 es 3, la etiqueta del nodo 4 es 4, y la etiqueta del nodo 5 es 2. El que tiene menor etiqueta es el nodo 5 por lo tanto, cerramos el nodo 5. Vamos a tratar de actualizar distancia a los nodos adyacentes a 5 pero, el nodo 5 no tiene ningún camino para llegar ni a 2 ni a 4. Por lo tanto, queda todo igual. Nuevamente, nos preguntamos cuál es el con menor etiqueta y es el nodo 2. Cerramos el nodo 2. Y vamos a comparar la etiqueta de si podemos actualizar el nodo 4. 3 más 3 es 6, es mayor que 4 por lo tanto, no podemos actualizar. Hemos terminado y hemos cerrado, entonces, el nodo 4. En las etiquetas de cada uno de los nodos, tengo el camino para llegar a ese nodo, a partir de los predecesores. Si yo quiero ver cuál es la ruta mínima para llegar al nodo 2, veo que la ruta mínima desde mi nodo fuente 1, tiene costo 3 y predecesor de acá es 2. Por lo tanto, este arco de acá. [AUDIO_EN_BLANCO] Es parte del árbol de rutas mínimas. Si yo me pregunto cuál es la ruta mínima para llegar a 4, veo que el predecesor acá es 3 y, por lo tanto, este arco también va a ser parte del árbol de rutas mínimas. Y si pregunto cuál es la ruta mínima para llegar a 5, es directamente desde el nodo 1 y su costo es 2, por lo tanto, este arco, también, es del árbol de rutas mínimas. En resumen, el árbol de rutas mínimas que hemos encontrado es este de acá al nodo 5, este de acá al nodo 3, este de acá al nodo 4 y este de acá al nodo 2. Este es nuestro árbol de rutas mínimas, conocemos también cuáles son las distancias asociadas a cada uno de ellos y hemos finalizado el algoritmo de Dijkstra.
