title: Are there faster algorithms than Dijkstra?
body: <p>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?</p>
  
  <p>Wikipedia says, that Dijkstra is in O(|E| + |V| * log(|V|)) (using a fibonacci heap).</p>
  
  <p>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)).</p>
  
  <p>Further, I would like to know your opinion on the following approach:</p>
  
  <ol>
  <li>Determine the GCD of all edge weights.</li>
  <li>Transform the graph into a graph with uniform edge weights.</li>
  <li>Use BFS to find the shortest path between two given vertices.</li>
  </ol>
  
  <p><em>Example for point 2:</em><br/>
  Imagine the GCD to be 1. Then I would transform the edge<br/>
  A--->B (edge weight 3)<br/>
  into<br/>
  A->A'->A''->B (3 times edge weight 1)<br/>
  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|)</p>
  
  <p>Thanks for taking the time to read my question and I hope not having waisted your time^^. Have a nice day.</p>