Dado un gráfico dirigido y conectado con solo ponderaciones de borde positivas, ¿hay algoritmos más rápidos para encontrar la ruta más corta entre dos vértices, que Dijkstra utilizando un montón de Fibonacci?

Wikipedia dice que Dijkstra está en O (| E | + | V | * log (| V |)) (utilizando un montón de Fibonacci).

No estoy buscando optimizaciones que, por ejemplo, la mitad del tiempo de ejecución, sino algoritmos que tienen una complejidad de tiempo diferente (como pasar de O (n * log n) a O (n)).

Además, me gustaría saber su opinión sobre el siguiente enfoque:

Determine el GCD de todos los pesos de borde.Transforma la gráfica en una gráfica con pesos de bordes uniformes.Usa BFS para encontrar la ruta más corta entre dos vértices dados.

Ejemplo para el punto 2:
Imagina que el GCD sea 1. Entonces transformaría el borde
A ---> B (borde de peso 3)
dentro
A-> A '-> A' '-> B (3 veces el peso del borde 1)
Esta transformación cuesta tiempo constante y debería realizarse una vez por cada borde. Así que espero que este algoritmo esté en O (| E |) (transformación) + O (| E | + | V |) (BFS) = O (2 * | E | + | V |) = O (| E | + | V |)

Gracias por tomarse el tiempo de leer mi pregunta y espero no haber perdido su tiempo ^^. Que tengas un buen día.