Least number of rides

I'm trying to solve this problem using an algorithm for at least a week but to no avail. I have a set of roads (1,2,3,...) and for each road there can be at least 1 vehicle that can pass (A,B,C,...). My problem is how to get the least number of rides for one to take to reach one road to another. For example:

road | vehicle(s)
  1  |  A,B
  2  |  A,B,C
  3  |  C,D
  4  |  C,D
  5  |  D,E

The output should be:

from 1, ride A or B to 2
from 2, ride C to 4
from 4, ride D to 5

The policy here is to exhaust one ride as much as possible, but the output should have the least number of ride changes.

Example 2:

road | vehicle(s)
  1  |  A,B
  2  |  A,B,C
  3  |  C,D
  4  |  C,D
  5  |  A,E
  6  |  E,F
  7  |  F
  8  |  F,H
  9  |  F,G
  10 |  F,G
  11 |  F
  12 |  F,G
  13 |  G,H
  14 |  H

Output:

from 1, ride A to 5
from 5, ride E to 6
from 6, ride F to 8
from 8, ride H to 14

Please help me to write the algorithm for the problem. I need to solve this for my proj开发者_高级运维ect. Thanks!

PS: If you need other examples or clarification, just tell me in the comments below.

One way to think about this problem is to model it as a graph search problem. For each of the different vehicles v, construct a graph G_v whose nodes are all of the roads in the network with arcs between the nodes that are connected by vehicle v. For example, in your first example, the graph G_A would have five nodes, of which there is only a connection from node 1 to node 2, while the graph G_C would have five nodes with edges from 2 to 3, 3 to 4, and 4 to 2.

Now, consider the final graph G constructed as follows. G is formed by taking all of the graphs G_v for all of the vehicles v (meaning that there are multiple copies of each node in the original graph), then adding edges between corresponding nodes in the different graphs if there are multiple different vehicles that all reach a road. For example, in the graph G for the original problem, you would have G contain subgraphs G_A and G_B, ..., G_E. Since road 1 is serviced by both vehicles A and B, you would add an edge between the nodes for road 1 in the graphs G_A and G_B, and since road 2 is serviced by vehicles A, B, and C, there would be edges connecting all of the road 2 nodes for subgraphs G_A, G_B, and G_C.

You are interested in minimizing the number of transfers you need to make, and so we'd like to set up some costs in this graph that measure that. In particular, we say that any edge contained completely in one of the subgraphs G_v has cost zero, since once you're on a vehicle of a given type you don't need to make any changes to move around the roads the vehicle services. However, we assign a cost of one to each of the edges linking the subgraphs for different vehicles, since following this sort of edge would mean that you're changing which vehicle you're using. If you now trace out any path in this graph, the total cost of that path is the number of vehicle changes you make.

To finalize the construction, we need to have some way of finding a cost from the starting road to the destination. To do this, we'll add two new nodes s and t to the graph representing the start and end of the journey. Node s will have cost-zero directed edges to the first road of each of the subgraphs, since when you start off the journey you can pick any of the vehicles as your first step. Similarly, every subgraph's node for the final road will have a zero-cost edge to t, since once you arrive at the destination road it doesn't matter what vehicle you're in.

In this setup, any path from s to t has a cost equal to the total number of transfers you need to make. Finding the shortest path in this graph from s to t therefore gives you both the route to take and the cost of that path. You can solve this using Dijkstra's algorithm, for example.

The runtime of this algorithm isn't stellar, but it's still polynomial time. Suppose that there are n roads and m different vehicles. The graph we create will have m different subgraphs in it, each of which is for one vehicle, and in the worst case these graphs have O(n²) edges in them. If we then link together all the corresponding nodes of these subgraphs where you can change lines, then in the worst case there will be O((mn)²) such edges, since there are m graphs of n nodes that all might be connected to one another. We thus have a graph with O(mn) nodes and O((mn)²) edges, so we can run Dijkstra's algorithm in O((mn)² + mn log mn) time.

The main idea that I think is important to take away from this problem is that you can often solve problems about finding paths in graphs subject to certain constraints by creating a new graph formed out of multiple copies of the old graph and then coming up with a good edge-cost function for that graph.

Hope this helps!