Finding the cheapest path with ignoring one cost

Question

I want to find the cheapest path between 2 vertices and I can choose one path which I can go for free., e.g:

Cheapest path between vertices 1 and 6 is 1-3-4-5-6 - I go on edge 1-3 (cost 30) for free and it gives me total cost 21.

Is there any other way than checking all paths one by one?

Answer 1

One way to do it would be to do the following:

1. Duplicate your graph, so that you have your original graph G with nodes 1,2,etc. and a copy G' with nodes 1',2',etc. and corresponding edges.
2. For each edge (a,b) of G, make an arc (directed!) from a to b' and another from b to a', both with cost 0.
3. Finally, use any shortest path algorithm from any vertex of subgraph G to any vertex of G' (1 to 6' in your example).

Basically what happens is that you switch from subgraph G to G' when you use your joker.

You can generalise from there to any number of joker edges by adding extra copies and linking each new one to the last. In that case however you may have to add targets using less jokers in order to account for the cases where the shortest path requires less edges than you have jokers.