Algoritmos y Estructuras de Datos (VJ1215)

Recordando el ejercicio 14 del tema 6, en la versión del algoritmo de Dijkstra que aparece en este apartado "Using a priority queue" de la página "Dijkstra's algorithm", se realizan estas operaciones con la cola de prioridad en el peor caso:

• O(|V|) veces add_with_priority (insertar)

• O(|V|) veces extract_min (consultar y eliminar el mínimo)

• O(|E|) veces decrease_priority (disminuir prioridad)

Si la cola de prioridad se implementa utilizando un montículo de Fibonacci, el coste en el peor caso del algoritmo lo obtenemos teniendo en cuenta los costes amortizados de esas operaciones: O(|V| + |V| log |V| + |E|) = O(|V| log |V| + |E|).