# Black and Yellow edges and Shortest path

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

-
Anyone? I know i need dijakstra here but i need something more to sole it. – Michael Cohen Jan 2 '13 at 16:35

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.
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