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.

Given directed and weighted graph $G=(V,E)$ . There is no negative weighted edge . Each edge is colored (black or yellow). I need to find an algorythm the find the shortest path for a given $s\in V$ while every path must be by this rule: $color(v_i\rightarrow v_{i+1}))=color(v_{i+3}\rightarrow v_{i+4})$ ,$\forall i :1\leq i\leq k-4$ while the path is $v_1 \rightarrow ... \rightarrow v_k$. The algorythm need to be in $O(|V|+E\cdot log(|V|))$

share|improve this question
    
Anyone? I know i need dijakstra here but i need something more to sole it. –  Michael Cohen Jan 2 '13 at 16:35
add comment

1 Answer

From the conditions on the colours in path, you can see that fixing the first $3$ colours fixes colours in entire path. Now consider $8$ different shortest path problems, one for each way to colour first $3$ edges in a path. In each shortest path problem, the paths have to follow that fixed colouring sequence. This can be handled in Dijkstra's algorithm. At each stage, you know the colour of next edge in the path, so consider only edges of that colour from that node. Once all $8$ problems are solved, for each node, you can just take minimum path length among these $8$. Complexity will be same as that of Dijkstra's, $O(|E|+|V|log|V|)$. It might be faster to solve all 8 sub-problems in one pass of the nodes.

share|improve this answer
    
thanks... it is $O(|V|+|E|\cdot log|V|)$ because you search for every $v \in V $ the minimum weighted path. –  Michael Cohen Jan 4 '13 at 15:50
    
@MichaelCohen: It can be improved to $O(|E| + |V|log|V|)$ by using fibonacci heaps for implementing the queue. –  polkjh Jan 4 '13 at 16:11
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.