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!
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
aún si como consecuencia insertar es 
. En otra implementación puede ser de interés que insertar sea , y se acepta que eliminar el mínimo sea . Y en otras se puede requerir un equilibrio y que todas las operaciones sean 
.
La implementación estándar para este algoritmo es con un heap que permite remover el mínimo, insertar y actualizar en y obtener el mínimo en .
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
aún si como consecuencia insertar es . En otra implementación puede ser de interés que insertar sea , y se acepta que eliminar el mínimo sea . Y en otras se puede requerir un equilibrio y que todas las operaciones sean . La implementación estándar para este algoritmo es con un heap que permite remover el mínimo, insertar y actualizar en
y obtener el mínimo en .