Suppose each edge can receive one of two weights $\{r_1,r_2\}$ where $r_1$ and $r_2$ are real and non-negative. And suppose $r_1 \leq r_2$. How do you find the shortest path from a given vertex s to every other vertex in the graph in linear time? ($O(V+E)$)
Shortest path in linear time
2
$\begingroup$
graph-theory
-
0A linear time algorithm for single source shortest path problem - http://www.ragibhasan.com/wp-content/uploads/publications/papers/hasan00linear.pdf – 2014-06-28