7.21. Análisis del algoritmo de Dijkstra¶

Finalmente, veamos el tiempo de ejecución del algoritmo de Dijkstra. Notamos en primer lugar que construir la cola de prioridad toma un tiempo $O (V)$ ya que inicialmente agregamos cada vértice del grafo a la cola de prioridad. Una vez construida la cola, el ciclo while se ejecuta una vez para cada vértice, ya que los vértices son todos agregados al principio y sólo se eliminan después. Dentro de ese ciclo, cada llamada a eliminarMin toma un tiempo $O (\log V)$ . En conjunto, esa parte del ciclo y las llamadas a eliminarMin toman un tiempo $O (V \log (V))$ . El ciclo for se ejecuta una vez por cada arista en el grafo, y dentro del ciclo for la llamada a decrementarClave toma un tiempo $O (E \log (V))$ . Así que el tiempo de ejecución combinado es $O ((V + E) \log (V))$ .