He intentado usar el algoritmo de Djikstra en el gráfico ponderado cíclico sin usar la cola de prioridad (Heap) y funcionó.

Luego busqué en Google que "¿por qué demonios necesitamos una cola de prioridad para implementar esto?" Como resultado de la búsqueda pasé por Wikipedia, donde pude saber que la implementación original no usa la cola de prioridad y se ejecuta en O (| V | 2), es decir, en V square time.

Ahora, si simplemente eliminamos la cola de prioridad y usamos la cola normal, el tiempo de ejecución es lineal, es decir, O (V + E).

Por favor, alguien sugiere, ¿por qué necesitamos cola de prioridad?