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))\).