Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Do you mean for every edge there is a weight? –  Thomas Andrews Aug 27 '12 at 17:59
    
Yeah, fixed. Thanks –  Jozef Aug 27 '12 at 18:05

2 Answers 2

up vote 7 down vote accepted

Create a new graph with the vertices being $V\cup V'$ where $V'$ is a replicate of the vertices of $G$ (meaning $|V'|=|V|$ 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.

share|improve this answer
    
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. –  joriki Aug 27 '12 at 17:55
    
@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. –  Belgi Aug 27 '12 at 18:11
    
@Belgi WOW! how did you come up with this? –  Zeta.Investigator Aug 27 '12 at 20:13
    
@PooyaMoradi - This type of reductions were very common in my Algorithm course –  Belgi Aug 27 '12 at 21:14

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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