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
add comment

2 Answers

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
add comment

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.

share|improve this answer
    
What's the deal? In a complete graph $|E|=O(|V|^2)$. –  Marc van Leeuwen Jan 8 '12 at 9:14
add comment

Your Answer

 
discard

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.