Dado um grafo direcionado e conectado com apenas pesos de borda positivos, existem algoritmos mais rápidos para encontrar o caminho mais curto entre dois vértices, do que Dijkstra usando um heap de fibonacci?

Wikipedia diz que Dijkstra está em O (| E | + | V | * log (| V |)) (usando uma pilha de fibonacci).

Eu não estou procurando por otimizações que, por exemplo, metade do tempo de execução, mas sim algoritmos que estão em uma complexidade de tempo diferente (como ir de O (n * log n) para O (n)).

Além disso, gostaria de saber sua opinião sobre a seguinte abordagem:

Determine o GCD de todos os pesos de borda.Transforme o gráfico em um gráfico com pesos de borda uniformes.Use o BFS para encontrar o caminho mais curto entre dois vértices dados.

Exemplo para o ponto 2:
Imagine o GCD como 1. Então eu transformaria a borda
A ---> B (peso da borda 3)
para dentro
A-> A '-> A' '-> B (3 vezes o peso da borda 1)
Essa transformação custa tempo constante e teria que ser feita uma vez para cada borda. Então eu espero que este algoritmo esteja em O (| E |) (transformação) + O (| E | + | V |) (BFS) = O (2 * | E | + | V |) = O (| E | + | V |)

Obrigado por tomar o tempo para ler a minha pergunta e espero não ter cintura o seu tempo ^^. Tenha um bom dia.