Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

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