Shortest path between two vertices when exactly on

Question

This is an interview question I came across:

You are given a the map of airplanes between the cities in a country, basically a directed graph was given with weights as the cost of planes between the cities. You were also given a single coupon to get 50% on any single flight. Find the minimum cost with which you can travel between two cities?

Answer 1

The base algorithm for this problem is Dijkstra's algorithm for shortest paths. However, we need to find a way to include the coupon.

We can do this by introducing the coupon state. It's either available or spent. At each airport, the state can be either of both. So we can duplicate the number of vertices (for airports). For each airport one vertex will have the available state and one will have the spent state. The edges have to be changed slightly. It's not possible to go from a vertex with the spent state to a vertex with the available state. In the other direction, the original cost halves.

Now we want to find the minimum cost path from the start airport (vertex with available state) to the destination airport (vertex with the spent state). This can be achieved with Dijkstra's plain algorithm.