CODEWITHSUNDEEP
algorithmshortest-pathdijkstra
Talor
Talor

Reputation: 81

How to make a faster algorithm

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.

Upvotes: 5

Views: 216

Answers (1)

Photon
Photon

Reputation: 2777

  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.

enter image description here

This gets transformed to this:

enter image description here

Upvotes: 5

Related Questions