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

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.

• Is this homework? Are you allowed to use outside help? – Yuval Filmus Apr 30 '16 at 20:44

## 1 Answer

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

• Okay, I thought about it a little more and understood. Thanks! – LiorGolan May 1 '16 at 9:24