EMMANUEL ALEJANDRO GARCÍA SOLÍS BLOG: HTTP://EMMANUELGS.BLOGSPOT.COM

Algoritmo de Dijkstra

Descripción:

El algoritmo de Dijkstra, también llamado algoritmo de caminos más cortos, es un algoritmo para la determinación del camino más corto dado un vértice origen.

Estructura de datos utilizada:

Este algoritmo utiliza un tipo de estructura de colas llamado cola de prioridad. Una cola de prioridad es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno.

Como funciona el Algoritmo?

1) Seleccionamos el nodo no visitado con menor distancia acumulada( al iniciar, este será siempre el nodo de inicio).

2) Sumamos la distancia acumulada en dicho nodo con la distancia de las aristas a los nodos a los que podemos acceder. Comparamos la nueva distancia con la que teníamos acumulada en el nodo destino (en caso de tener ya alguna) y nos quedamos con la menor.

3) Marcamos el nodo actual como visitado y volvemos al paso 1.

Ejemplo paso a paso:

Complejidad

El Algoritmo de Dijkstra realiza O(v2) 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, esto sin utilizar cola de prioridad.

O((|E|+|V|) log |V|) utilizando cola de prioridad (por ejemplo un montículo).

Uso

Este algoritmo se usa bastante en redes de computadores, los nodos corresponden a routers y las aristas entre ellos las conexiones, a cada conexión se le asigna un costo (distancia) y de esta manera algunos protocolos de enrutamiento usan el algoritmo de Dijkstra para encontrar la mejor ruta entre nodos.

Bibliografía

http://www.youtube.com/watch?v=6rl0ghgPfK0

http://156.35.31.178/wiki/index.php/TP:Algoritmo_de_Dijkstra_-_Algoritmos_voraces

http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra