Dijkstra

Dijkstra

de Nicolas Grosso San Roman -
Número de respuestas: 1

Hola! En la implementaciçon de Dijkstra dice que cada nodo perteneciente a V lo insertamos en una cola de prioridad, esto no es O(n)? Cómo afecta esto al orden propuesto de O(mlog n)? Gracias!

En respuesta a Nicolas Grosso San Roman

Re: Dijkstra

de Fernando Fernandez -
Hola Nicolás.

Puede haber muchas implementaciones de cola de prioridad, teniendo compromisos entre distintas operaciones. O sea, en alguna implementación interesa obtener el mínimo en O(1) aún si como consecuencia insertar es \Theta(n). En otra implementación puede ser de interés que insertar sea O(1), y se acepta que eliminar el mínimo sea \Theta(n). Y en otras se puede requerir un equilibrio y que todas las operaciones sean O(\log n).

La implementación estándar para este algoritmo es con un heap que permite remover el mínimo, insertar y actualizar en O(\log n) y obtener el mínimo en O(1).