Algoritmo de Dijkstra [PDF]

Zitiervorschau

Universidad Nacional Experimental de Guayana. Vicerrectorado Académico. Coordinación de Ingeniería en Informática. Investigación de operaciones.

Profesor: Medina Luz

Integrantes: Planes Felipe Ruíz Ana

Algoritmo de Dijkstra

(camino mínimo, ruta más corta, árbol mínimo) El algoritmo de Dijkstra, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de los vértices con pesos en cada arista, en un grafo conexo no dirigido. Su nombre se refiere a Edsger Dijkstra, un físico y científico de la computación quien lo describió por primera vez en 1959.

Fuente:

Descripción del algoritmo La idea subyacente en este algoritmo consiste en: • Ir explorando todos los caminos 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. Este algoritmo es una especialización de la búsqueda de costo uniforme (BCU), y como tal, no funciona en grafos con aristas de coste 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).

Fuente:

Complejidad del algoritmo. El Algoritmo de Dijkstra realiza O(n²) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.

• O(|V|2+|A|) = O(|V|2) sin utilizar cola de prioridad. • O((|A|+|V|) log |V|) = O(|A| log |V|) utilizando cola de prioridad (por ejemplo un montículo).

Fuente:

Aplicaciones en la informática Encaminamiento de paquetes por los routers: En un momento dado, un mensaje puede tardar cierta cantidad de tiempo en atravesar cada línea (por ejemplo, por efectos de congestión). En este caso, tenemos una red con dos nodos especiales, el de inicio y el de llegada. Los pesos de las aristas serían los costes. El objetivo del algoritmo es encontrar un camino entre estos dos nodos cuyo coste total sea el mínimo.

Fuente:

Aplicaciones en la informática Sistemas de información geográficos: Extracción de características curvilíneas de imágenes usando técnicas de minimización del camino. La imagen se representa como una matriz de puntos, cada uno con una intensidad. Cada nodo es un punto (píxel) de la imagen. El peso de las aristas es la diferencia de color.

Fuente:

Aplicaciones en la informática Enrutamiento de aviones y tráfico aéreo:

Consiste en un agente de solicitudes de viaje software para hacer un programa de vuelos para los clientes. El agente tiene acceso a una base de datos con todos los aeropuertos y los vuelos como el número de vuelo, el aeropuerto de origen y destino y los horarios de salida y de llegada. La aplicación se usa para determinar la hora de llegada más temprana para el destino dado un aeropuerto de origen y hora de inicio.

Fuente:

(utilizando nuestro software)

¿Algunas preguntas?