0
$\begingroup$

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?

$\endgroup$
3
2
$\begingroup$

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$.

Now you can use a standard unweighted pathfinding algorithm, such as BFS.

$\endgroup$
2
  • $\begingroup$ Thank you very much. $\endgroup$ Jul 31 at 18:24
  • $\begingroup$ 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$. $\endgroup$
    – Brian
    Jul 31 at 20:04

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.