Shortest Path in Graph, when it is obligatory to jump over every second edge

Question

I`ve been preparing myself for programming competition and I stumbled upon this problem, in which I have to find shortest path from source to destination in weighted and undirected graph, but I have to skip every second edge (so its weight is not important). Weight in graph are positive integers.

Original statement:

Clara and Jake are on trip. They are driving in turns and car driver is being changed after every city. Find shortest path from source to destination, that Clara drove least miles. Write who should be car driver first.

What is the best approach to solve this problem? Is there any modification of any algorithm to solve it easy?

Edit: jumped edges has weight equal to 0, if edge can be skipped or not I have to check both options.

Answer 1

If I understood correctly you want to find the shortest path in a weighted graph with the additional complexity that the weight of a path is the sum of the weight of the odd edges (1, 3, ...) or the even edges (2, 4, ...) along the path.

You can do this by first creating a new graph:

1. for each vertex v in the original graph, create two vertices in the new graph, one will be called even v and the other one odd v
2. if (u, v) is an edge of weight w in the original graph, add the following edges to the new graph: (even u, odd v) with weight w and (odd u, even v) with weight 0

Then do two usual Dijkstra to find the shortest path reaching odd destination and even destination from even source. The one with the smallest weight is the shortest path if Clara is first to drive.

Do the same procedure, starting from odd source to find the shortest path if Clara is driving second.

Proof

The invariant we want to have in the new graph is:

• even v is a vertex reached through a path whose last edge is even numbered
• odd v is a vertex reached through a path whose last edge is odd numbered

As we only add edges from even to odd and from odd to even this invariant is true for the whole new graph. We use a weight of 0 for even numbered edges to accomodate the special weighting function for paths.

The source in the original graph maps to the even source in the new graph has it is reached by a path containing 0 edges if Clara drive firsts. When Clara drives second, source maps to odd source.

destination in the original graph may map to either even destination or odd destination depending on the number of edges on the path. By taking the shortest weighted path to either we are sure to find the shortest path using the special weighting function in the original graph.

Answer 2

For every pair of adjacent edges insert pair of directed edges as on the picture, here i assume that first edge in every pair isn't counted.

Now you need to find shortest path in directed graph but not to destination vertex, instead find shortest paths to the destination vertex and to all vertices at distance 1 from the destination vertex and now you can easily deduce the shortest path length.