ALGORITMO DE DIJKSTRA
HISTORIA
Edsger Wyde Dijkstra
Nacido en Rotterdam, (Holanda) en 1930, su padre era químico y su madre matemática. con 12 años, entró en Gymnasium Erasminium, una escuela para estudiantes especialmente brillantes, donde dio clases de Griego, Latín, Francés, Alemán, Inglés, biología, matemáticas y química.
Debido a su facilidad para la química, las matemáticas y la física, entró en la Universidad de Leiden, donde decidió estudiar física teórica. Después de asistir a un curso de programación en la Universidad de Cambridge, empezó a trabajar en el Centro Matemático en Amsterdam, donde se incrementó su creciente interés en la programación. Cuando terminó la carrera se dedicó a problemas relacionados con la programación.
El resto de su vida se dedico a la investigación y desarrollo de diversos problemas de programación hasta su reciente muerte en el año 2002
En 1959, Dijkstra anunció su algoritmo de caminos mínimos o también llamado ruta mas corta o árbol mínimo
Propuesto en 1959 el algoritmo de caminos mínimos o también llamado ruta mas corta o árbol mínimo o simplemente algoritmo de Dijkstra es un algoritmo para determinar el camino o ruta mas corta desde un nodo de origen hacia los demás nodos del grafo, en el cual cada arista o arco posee un peso. Se siguen una serie de pasos y consideraciones que veremos a continuación
PASOS PARA SU APLICACIÓN
Para realizar la aplicación del algoritmo de Dijkstra, se aplican los siguientes pasos:
1. Se elige un nodo de inicio al cual se le marcara un peso de la siguiente forma:
[X,Y](N)
Donde ‘X’ equivale a el valor del recorrido actual de los arcos, ‘Y’ equivale a el nodo predecesor o de origen y ‘N’ al numero de iteración u operación actual
2. A los nodos adyacentes del nodo seleccionado como nodo de inicio, se deben asignar un peso de igual forma al punto anterior, ( [X,Y](N) )
3. De los nodos con los pesos calculados se toma el nodo con menor valor en X y este será el siguiente a visitar
4. Los pasos 2 y 3 deben repetirse teniendo en cuenta que si al intentar calcular los pesos para los nodos adyacentes a un nodo que esta siendo visitado, uno de estos ya tiene un peso asignado, deben calcularse los demás pesos cuantas veces sean necesario, y siempre se tomara el peso mínimo calculado
5. Los nodos pueden ser visitados una sola vez
Ejemplo de aplicación: Nodo de inicio A
Pseudocódigo
Dijkstra (G,s)
Inicializar
for cada v perteneciente a V[G]
do d[v] = infinito
p[v] = nulo
d[s] = 0
S = vacio
Q = V[G]
mientras Q no vacío
do u = nodo v con min d[v]
S = S unión u 'se añade al conjunto de nodos finalizados
for cada v perteneciente Adyacente u
if d[v] > d[u] + w(u,v) then
d[v] = d[u] + w(u,v)
p(v) = u
APLICACIONES
•Encaminamiento de paquetes por routers
•Enrrutamiento de Aviones y trafico aéreo
•Movilidad terrestre
•Sistemas de geolocalizacion
Bibliografía
•https://jariasf.wordpress.com/2012/03/19/camino-mas-corto-algoritmo-de-dijkstra/
[if ppt]•[endif]
•http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_dijkstra
[if ppt]•[endif]
•http://arxiv.org/pdf/0810.0075.pdf
Tutoriales
[if ppt]•https://www.youtube.com/watch?v=LLx0QVMZVkk[endif]
•https://www.youtube.com/watch?v=fgdCNuGPJnw
[endif]
•https://www.youtube.com/watch?v=VENf0GXRd6E
