3
$\begingroup$

Given a directed graph $G=(V,E)$, and a vertex $s\in V$, for every edge there's an integer weight $w(e)$ (positive or negative), I need to find an algorithm such that for every vertex $v \in V$ it finds the shortest path (by weights) which contains an even number of edges. (I can assume it doesn't have a negative cycles).

Obviously I need to use Bellman-Ford with complexity of $O(|V||E|)$, but how do I manipulate it in such way that the paths will contain an even number of edges?

Thanks!

$\endgroup$
2
  • $\begingroup$ Do you mean for every edge there is a weight? $\endgroup$
    – Thomas Andrews
    Commented Aug 27, 2012 at 17:59
  • $\begingroup$ Yeah, fixed. Thanks $\endgroup$
    – Jozef
    Commented Aug 27, 2012 at 18:05

3 Answers 3

Reset to default
8
$\begingroup$

Create a new graph with the vertices being $V\cup V'$ where $V'$ is a replicate of the vertices of $G$ (meaning $\mid V'\mid=\mid V\mid$ and the sets are disjoint).

The edges are: $$e'=(i,j')\in E' \iff e=(i,j)\in E$$ $$e'=(i',j)\in E' \iff e=(i,j)\in E $$

(there are no edges of the form $(i,j),(i',j')$.

The weights are $w'((i,j'))=w'((i',j))=w((i,j))$.

Now, any path from $i$ to $j$ must be of even length (paths of odd length end up in $V'$ and not in $V$).

Now you can use Bellman-Ford.

$\endgroup$
4
  • $\begingroup$ This is basically the same as my answer. If you already have an implementation of the Bellman-Ford algorithm and it's easier to mess with the graph than to mess with the code, this is the better formulation; if it's easy to modify the code or you're writing it yourself anyway, my formulation might be a bit less cumbersome. $\endgroup$
    – joriki
    Commented Aug 27, 2012 at 17:55
  • $\begingroup$ @joriki - I wrote my answer before I saw yours. I agree about the idea. the reason I done this in this way is that in my Algorithms course we were not allowed to change existing algorithms withouht formally prove everything from the start (even if the change was trivial) so the idea was always to make a reduction to use existing algorithms. $\endgroup$
    – Belgi
    Commented Aug 27, 2012 at 18:11
  • $\begingroup$ @Belgi WOW! how did you come up with this? $\endgroup$
    – Zeta.Investigator
    Commented Aug 27, 2012 at 20:13
  • $\begingroup$ @PooyaMoradi - This type of reductions were very common in my Algorithm course $\endgroup$
    – Belgi
    Commented Aug 27, 2012 at 21:14
2
$\begingroup$

You can do something similar as in this answer: Maintain two separate distances from the source to each vertex, one for paths with an odd number of edges, one for paths with an even number of edges. In each update, use the odd ones to update the even ones and vice versa.

$\endgroup$
2
$\begingroup$

The answers from @Belgi and @joriki are erroneous because they only find the shortest walk (i.e it can go through an edge more than once): The shortest path in the bipartite graph can pass through both $(i, j')$ and $(i', j)$ in $E'$, which result in $(i, j)$ taken twice in $G$ (with notations from @Belgi answer).

The problem of the shortest even path in directed graphs is in fact $\mathcal{NP}$-hard but is polynomial in undirected graphs. See:
LaPaugh, Andrea S.; Papadimitriou, Christos H., The even-path problem for graphs and digraphs, Networks 14, 507-513 (1984). ZBL0552.68059.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .