How to make a faster algorithm

Question

Let 𝐺 = (𝑉, 𝐸) be a directed graph with edge weights and let 𝑠 be a vertex of 𝑉. All of the edge weights are integers between 1 and 20. Design an algorithm for finding the shortest paths from 𝑠. The running time of your algorithm should be asymptotically faster than Dijkstra’s running time.

I know that Dijkstra’s running time is O( e + v log v), and try to find a faster algorithm.

If all weights are 1 or only include 0 and 1, I can use BFS O(e+v) in a directed graph, but how to make a faster algorithm for edge weights are integers between 1 and 20.

Answer 1

1. Well let`s say you have an edge that goes from u to v with weight w
2. We can insert w-1 extra nodes between nodes u and v
3. So after modifying each edge (which takes O(20*E)) we have a graph where every edge is 1
4. And on such graph we can use regular BFS, we will have atmost 20*N new nodes, and 20*E new edges so complexity is still O(V+E)

i.e.

This gets transformed to this: