# An "easy" graph problem I can't solve

The question is:

A given graph is given with only weights 1 or 2 on its arcs. (I.e. each arc has a weight of 1 or a weight of 2)

And a origin vertex s.

Write an efficient algorithm that finds the shortest paths (most easy in weight that is) from s to the rest of the vertices.

I really don't have a better idea than perform the Dijkstra algorithm, but I know it is not the right answer. Help anyone?

For every edge $$(u,v)$$ with weight $$2$$, create a new node $$w_{u,v}$$. Discard the edge $$(u,v)$$, and instead of it add two edges $$(u,w_{u,v})$$ and $$(w_{u,v},v)$$ with weight $$1$$.
• I look at Dijkstra's algorithm on a weighted graph $G$ as actually an "efficient" BFS on an unweighted $G'$ graph -- where each edge $(u,v)$ of weight w in $G$ has been replaced by a path of length $w$ formed of unweighted arcs from $u$ to $v$. Jul 31 at 20:04