Algoritmo de Dijkstra

Algoritmo de Dijkstra

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   

Algoritmo de Dijkstra

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

Pasos para su aplicación

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

Enrutamiento de Aviones y trafico aéreo

Movilidad terrestre

Sistemas de geolocalisacion