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 so$u$rce shortest path problem - http://www.ragibhasan.com/wp-content/uploads/publications/papers/hasan00linear.pdf2014-06-28

1 Answers 1

3

The asymptotically best algorithm known for this (well studied) problem is an implementation of Dijkstra'a algorithm, which runs in $O(|E|+ |V|\log|V|)$ time. That is almost but not quite as good as you asked for, so probably you just asked too much.