Имеют ли ориентированный связный граф только с положительными весами ребер, есть ли более быстрые алгоритмы для нахождения кратчайшего пути между двумя вершинами, чем Дейкстра, использующий кучу Фибоначчи?

Википедия говорит, что Дейкстра находится в O (| E | + | V | * log (| V |)) (используя кучу Фибоначчи).

Я не ищу оптимизацию, которая, например, вдвое меньше времени выполнения, а скорее алгоритмы, которые имеют разную временную сложность (например, переход от O (n * log n) к O (n)).

Кроме того, я хотел бы узнать ваше мнение о следующем подходе:

Определите GCD всех весов ребер.Преобразуйте график в граф с равномерным весом ребер.Используйте BFS, чтобы найти кратчайший путь между двумя заданными вершинами.

Пример для пункта 2:
Вообразите, что GCD равен 1. Тогда я бы преобразовал край
A ---> B (вес ребра 3)
в
A-> A '-> A' '-> B (3-кратный вес ребра 1)
Это преобразование стоит постоянного времени и должно быть выполнено один раз для каждого края. Поэтому я ожидаю, что этот алгоритм будет в O (| E |) (преобразование) + O (| E | + | V |) (BFS) = O (2 * | E | + | V |) = O (| E | + | V |)

Спасибо, что нашли время, чтобы прочитать мой вопрос, и я надеюсь не тратить ваше время ^^. Хорошего дня.