Anexo Opcional A: Algoritmos de Dijkstra

Loading...

Del curso dictado por Pontificia Universidad Católica de Chile

Análisis de Sistemas de Transporte

335 calificaciones

Pontificia Universidad Católica de Chile

Análisis de Sistemas de Transporte

335 calificaciones

Este curso es una introducción a las metodologías fundamentales para la gestión, planificación y evaluación de sistemas de transporte de pasajeros. Se aprenderán técnicas usadas en la práctica para estimar la demanda, modelar la operación y realizar análisis económicos de proyectos de transporte. Algunos temas estudiados incluyen: modelo clásico de transporte de cuatro etapas, modelo de distribución de viajes gravitacional, modelo de elección discreta logit, teoría de colas, análisis de redes, paradoja de Braess, tarificación por congestión y evaluación social de proyectos de transporte.

De la lección

Equilibrio de sistemas de transporte

El objetivo de este módulo es que comprendas cómo el sistema puede alcanzar el equilibrio, y los distintos estados a los que puede llegar. A partir de esto podrás identificar y saber cómo solucionar una serie de fenómenos que aparecen en las redes de transporte.

Equilibrio de usuarios y óptimo de sistemas12:01

Anexo Opcional A: Algoritmos de Dijkstra9:29

Anexo Opcional B: Transformada de Beckmann y problema de optimización9:57

Conoce a los instructores

Ricardo Giesen
Profesor Asociado
Ingeniería de Transporte y Logística, Centro de Desarrollo Urbano Sustentable (CEDEUS, www.cedeus.cl); Centro de Excelencia en BRT (www.brt.cl); Centro de Gestión de Desastres Naturales (CIGIDEN, www.cigiden.cl)
Felipe Delgado
Profesor Asistente
Ingeniería de Transporte y Logística, Centro de Desarrollo Urbano Sustentable (CEDEUS), All Latitudes and Cultures BRT Centre of Excellence (www.brt.cl)
Juan de Dios Ortuzar
Profesor Emérito
Departamento de Ingeniería de Transporte y Logística, Centro de Desarrollo Urbano Sustentable (CEDEUS), All Latitudes and Cultures BRT Centre of Excellence (www.brt.cl)

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

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play