finding shortest path in a weighted graph

 

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?

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.

    If you can calculate the distance in straight line between two cities, you can use A* instead of Dijkstra, using that function of distance as heuristic. For sure you will expand fewer nodes than with Dijkstra.

    Regarding the airways, your approach sounds fine.

    Create an auxiliary directed graph G' th following way.

    For each city V in the main graph G add two cities V' and V'' to G'.

    For each road VW in G add four one-way roads V'W', W'V', V''W'', W''V'' to G'.

    For each air connection VW in G add two one-way connections V'W'' and W'V'' to G'.

    The resulting graph is directed and partitioned in two subgraphs such that you can only travel from the first subgraph to the second by air, and cannot travel back. This ensures you can use an air eg at most once.

    You can run the Dijkstra algorithm on G'. Now shortest path between S and T in G will correspond to the shorter of two paths in G': one between S' and T' (ground only) and one betweeen S' and T'' (exactly one air transfer).

    链接地址: http://www.djcxy.com/p/35234.html

    上一篇: 在N个步骤内直接绘制非循环图最短路径

    下一篇: 在加权图中找到最短路径