2
$\begingroup$

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

  • 0
    A linear time algorithm for single source shortest path problem - http://www.ragibhasan.com/wp-content/uploads/publications/papers/hasan00linear.pdf2014-06-28

1 Answers 1