finding shortest path in a weighted graph

Question

Given is a graph of cities and cost of airways and roadways as edge weights between each pair of cities. We need to find min. cost to travel from source city to destination city given the constraint that I can travel through airways at max only once.

My approach so far: selecting each airways edge once then apply dijkstra to the remaining graph only on the roadways edges. Is there any way to improve this?

Answer 1

Construct a directed graph (G, E) as follows:

Let X be the source city and Y be the destination city.

For every city C other than X, construct two vertices: (C, yes) and (C, no), where "yes" means "airplane used" and "no" means "airplane unused". For the source city X, only construct one vertex (X, no).

The edges are as follows:

• There is no edge from any (C, yes) to any (D, no).
• There is an edge from (C, yes) to (D, yes) (resp. (C, no) to (D, no)) if and only if there is roadway between C and D, and the weight of this edge is the weight of the roadway.
• There is an edge from (C, no) to (D, yes) if and only if there is airway between C and D, and the weight of this edge is the weight of the airway.

Now, simply find the shortest path in the graph G from (X, no) to (Y, yes) (resp. to (Y, no)), which is the minimum cost using exactly one airway (resp. using no airway). The minimum of these two will be the final answer.

---

The complexity will be the complexity of shortest path problem for the directed graph (G, E), which (up to big O constant) has the same number of vertices and edges as the original graph.

According to this wiki page, this problem can be solved in O(E+VloglogV) time. You can of course use Dijkstra for simplicity.