3
$\begingroup$

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the shortest way with the minimum even weight.

I'd like to have some ideas how we solve this.

Thanks.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Hint, two problems are easier than one problem sometimes. Consider also calculating the SSSP with odd weight at the same time. $\endgroup$ – Apass.Jack May 17 at 13:34
  • $\begingroup$ @Apass.Jack Thank you. So if I understood you, now having in hand odd and even shortest way, for every new edge, if it's odd I modify the even shortest path I have in hand and if it's even I modify the odd? And at last I return the even? $\endgroup$ – Sama Assi May 17 at 13:55
3
$\begingroup$

Forget the even-length requirement for a moment and consider how something like Dijkstra's algorithm works. As the algorithm progresses, you have essentially two types of vertex: the ones for which you've already figured out the shortest path, and the ones for which you only have an upper bound (i.e., the shortest path you've seen to that vertex so far).

Modify it so there are three types of vertex: ones for which you've figured out the shortest even-length path, ones for which you've figured out the shortest path but it was odd, and ones for which you only have an upper bound for the shortest path and shortest even path.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you. So if I understood you, now having in hand odd and even shortest way, for every new edge, if it's odd I modify the even shortest path I have in hand and if it's even I modify the odd? And at last I return the even? $\endgroup$ – Sama Assi May 17 at 13:55
  • 1
    $\begingroup$ Actually, both. Suppose there's an edge $xy$ of weight $1$ and you know the shortest odd and even paths to $x$. Then the even path plus $xy$ is an odd path to $y$, and the odd path plus $xy$ is an even path. $\endgroup$ – David Richerby May 17 at 14:10
  • $\begingroup$ And what happens in case that there are no such path? (even weight path)? How can I tell? $\endgroup$ – Sama Assi May 17 at 14:17
  • 1
    $\begingroup$ You'll probably end up with the "shortest" path having length $\infty$ in that case. $\endgroup$ – David Richerby May 17 at 14:18
  • $\begingroup$ But in this case (for every edge we edit both odd and even path's weights), we can end up with a value at the even path but it's not valid. How would we know it's not valid and we have to return ∞? $\endgroup$ – Sama Assi May 17 at 14:24
2
$\begingroup$

Another solution that doesn't require modifying the algorithm (so you can do it with an off-the-shelf implementation):

Have two copies of the graph, one called even the other called odd. The idea is that when the total path-length so far is even/odd, you'll be in the even/odd graphs respectively. Then you only need to consider the start/end nodes on the even graph.

You can do this by removing the odd-length edges from both graphs, and replacing them with equivalent edges that criss-cross graphs. This works because adding an odd number swaps parity, while adding an even number keeps the same parity.

|cite|improve this answer
$\endgroup$

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.