# Shortest path in linear time

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

-
A linear time algorithm for single source shortest path problem - ragibhasan.com/wp-content/uploads/publications/papers/… –  user160606 Jun 28 at 12:12

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.
I assume you are talking about worst-case complexity. Unless you are thinking about a specific class of admissible graphs (acyclic ones, for example), what you are asking for is impossible. If $r_1 = 0$ and $r_2 = 1$, and every edge is given weight $r_2$, and every edge is assumed to be doubly directed, the problem reduces to the traditional non-weighted shortest path problem for undirected graphs. The complete graphs then tell us that there is a $\Omega(|V|^2)$ lower bound on the worst-case complexity of any algorithm.
What's the deal? In a complete graph $|E|=O(|V|^2)$. –  Marc van Leeuwen Jan 8 '12 at 9:14