# How to achieve Dijkstra's O(X+Y) in time complexity if edge weights always is 1 or 2?

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.

• Think where does the $O(\log n)$ in Dijkstra comes from and figure out how to deal with that given this special restriction. – Christopher Boo Mar 12 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)$$