If we were to have a connected directed graph that has X edges and Y vertices and all the edge weights are either 1 or 2. Would it be possible to somehow achieve a time complexity of O(X+Y) using Dijkstra's algorithm, when finding the shortest path between the two given vertices A and B from the graph.

  • $\begingroup$ Think where does the $O(\log n)$ in Dijkstra comes from and figure out how to deal with that given this special restriction. $\endgroup$ – Christopher Boo Mar 12 '19 at 5:17

If all edge weights are $1$ or $2$ you can have a linear time algorithm to find shortest path. First perform a BFS and for every edge $(u,v)$ of weight $2$ add an vertice at the middle $w$ so that you now have two edges of weight one $(u,w)$ and $(w,v)$.

After this BFS your new graph have all it edges of weight $1$ and have at most $2X$ edges.

Now perform an other BFS on this graph to find the shortest path. It gives you a complexity of $O(2X+Y)$. Thus the total complexity is $O(X+Y)$

| cite | improve this answer | |
  • $\begingroup$ After the first BFS, the new graph has a different number of vertices, doesn't it? Something in [Y, 2Y)? That still gets the same end answer, but it should be O(2X + 2Y) -> O(X + Y). Is that wrong? $\endgroup$ – Adam Mar 13 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.