0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Is this homework? Are you allowed to use outside help? $\endgroup$ – Yuval Filmus Apr 30 '16 at 20:44
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.