Shortest path in “two-graph” with limited number o

问题:

Let's say we have two directed and positive-weighted graphs on one set of vertices (first graph represents for example rail-roads and the second one - bus lanes; vertices are bus stops or rail-road stations or both). We need to find the shortest path from A to B, but we can't change the type of transport more than N times.

I was trying to modify the Dijkstra's algorithm, but it's working only on a few "not-so-mean-and-complicated" graphs and I think I need to try something different.

How to best represent that "two-graph" and how to manage the limited amount of changes in traversing the graph? Is there a possibility to adapt Dijkstra's algorithm in this one? Any ideas and clues will be helpful.

Edit: Well I forgot one thing (I think it's quite important): N = 0,1,2,...; we can come up with any graph representation we like and of course there can exist maximum 4 edges between every two nodes (1 bus lane and 1 railroad in one direction, and 1 bus lane and 1 railroad in the second direction).

回答1:

I don't think it is the best way, but you can create Nodes as follow:

Node:(NodeId, GraphId, correspondenceLeftCount)

(the total number of nodes will be number_of_initial_nodes * number_of_graphs * number_of_correspondences_allowed)

So:

For edge where GraphId doesn't change, correspondenceLeftCount doesn't change neither. You add a new Edge for correspondance:

(NodeId, Graph1, correspondenceLeftCount) -> (NodeId, Graph2, correspondenceLeftCount - 1)`

And for the request A->B: Your start point are (A, graph1, maxCorrespondenceLeftCount) and (A, graph2, maxCorrespondenceLeftCount).
And your end points are (B, graph1, 0), ... , (B, graph1, maxCorrespondenceLeftCount), (B, graph2, 0), ... , (B, graph2, maxCorrespondenceLeftCount).

So you may to have to adapt your Dijkstra implementation for the end condition, and to be able to insert more than one start point.