Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer 1

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.