Algoritmo de Dijkstra

Su nombre alude a Edsger Dijkstra, científico de la computación de los Países Bajos que lo concibió en 1956 y lo publicó por primera vez en 1959.[1]​[2]​ 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 hasta el resto de los vértices que componen el grafo, el algoritmo se detiene.Orden de complejidad del algoritmo: La complejidad computacional del algoritmo de Dijkstra se puede calcular contando las operaciones realizadas: Luego, en cada iteración se realizan a lo sumo 2(n-1) operaciones.Entonces: Teorema: El algoritmo de lpz 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.En general: Estructura de datos auxiliar: Q = Estructura de datos cola de prioridad (se puede implementar con un montículo) Al final, tenemos en el vector distancia en cada posición la distancia mínima del vértice salida a otro vértice cualquiera.Una vez planteadas todas las restricciones del modelo que garantice que se va a cumplir el algoritmo de Dijkstra en la red, se procede a resolver el modelo mediante algún software que permita obtener la solución óptima de dicho modelo.