Are there faster algorithms than Dijkstra?

Question

Given a directed, connected graph with only positive edge weights, are there faster algorithms for finding the shortest path between two vertices, than Dijkstra using a fibonacci heap?

Wikipedia says, that Dijkstra is in O(|E| + |V| * log(|V|)) (using a fibonacci heap).

I'm not looking for optimizations that, for example, half the execution time, but rather algorithms that are in a different time complexity (like going from O(n * log n) to O(n)).

Further, I would like to know your opinion on the following approach:

1. Determine the GCD of all edge weights.
2. Transform the graph into a graph with uniform edge weights.
3. Use BFS to find the shortest path between two given vertices.

Example for point 2:
Imagine the GCD to be 1. Then I would transform the edge
A--->B (edge weight 3)
into
A->A'->A''->B (3 times edge weight 1)
This transformation costs constant time and would have to be done once for every edge. So I expect this algorithm to be in O(|E|) (transformation) + O(|E| + |V|) (BFS) = O(2 * |E| + |V|) = O(|E| + |V|)

Thanks for taking the time to read my question and I hope not having waisted your time^^. Have a nice day.

Answer 1

The big oh analysis you did for your algorithm is deeply flawed. Assume all edges are prime numbers. The number of edges in the new graph will be equal to sum of all weights. Thus O(|E| + |V|) of the new graph is actually O(W x |E| + |V|) in the original graph which can be much larger than O(|E| + |V| log |V|).