Find all shortest paths in a graph where path has even number of edges and greater than 6

Question

Let $G=(V,E)$, a directed with non-negative weights ($w:E\to\mathbb{R}^+$). Describe an algorithm, finds all shortest paths in the graph from a source vertex, $s\in V$, such that, each paths has an even number of edges and the number of edges is greater-equal to $6$.

So I know I need to use Dijkstra algorithm on a modified graph. Somehow I need to "count" the number of edges. I think I need to add some vertices for each vertex which will make the "count" but I can't figure it out completely.

I'd be glad for help.

Thanks.

Answer 1

Hint: Use an appropriate layered graph. If you find the problem difficult, try solving it under only one of the conditions (only an even number of edges, or only at least 6 edges).