Algorithm for shortest path at the same time least transfers

I have already made a directed graph with costs (distance between each station) for three shuttle routes. The fare from station to station of any shuttle route is the same therefore the only thing to do is to minimize transfers.

I want it to work this way. I want to go from Station A -> C. Let's assume first that the d开发者_StackOverflow社区istance between stations is one (1) for simplicity.

Route 1: A -> D -> B -> C -> A
Route 2: A -> C -> E -> F -> A
Route 3: A -> X -> Y -> Z -> A

Since there is a path from A -> C in both Routes 1 and Routes 2, I will choose one with least cost which is Route 2. I have already done this.

But if I want to go from Station C -> Y, there is no direct route from C -> Y. So I have to go either from 1 or 2 then hop off at A then from A -> Y. Basically, I just want to minimize the shuttle transfers and distance traveled.

Is there a popular algorithm for this?

You can solve this with Dijkstra's algorithm.

Set up a graph so that:

There is a node for each station on a shuttle route. If two shuttles go to the same staton, then that station gets one node for each route. So in your example there are nodes A1, D1, B1, C1, A2, C2, E2, F2 -> A2, etc. Also create a node for each station, but make it independent of the route, e.g., A, B, C, etc.

If a shuttle travels directly between two stations, e.g., in your example between A1 and D1 but not between A1 and B1, then create a directed edge between those two nodes. The weight for that edge should be the cost (distance) between the two stations. So, for example, there are edges (A1, D1) and (D1, C1)

If two shuttles stop at the same station then create two directed edges between the nodes for the station on the two routes, e.g., create edges (A1, A2) and (A2, A1). The weight for the edges should be the cost for a transfer.

Create two edges between each route-specific station node and the station node that is independent of the station, e.g., create edges (A, A1), (A1, A), (A, A2), (A2, A). Give each of these nodes a cost that is much smaller than the costs of the previous edges, e.g., .01 * the minimum cost.

Now if you want to travel between two stations, use Dijkstra's algorithm to find the lowest-cost path between the two non-route specific nodes.

In your example, to travel from F to X, find the lowest-cost path between nodes F and X. The path returned will be F -> F2 -> A2 -> A3 -> X3 -> X with means start at F, get on shuttle 2, travel to A, transfer to route 3 then get off at station X.

lots, and lots of optimisations for certain scenarios, constraints etc.

try dijkstra's, its usually the basis for shortest path algorithms (i.e. where lots of people start to learn about that topic), although to really understand how it can be efficiently implemented, you should probably also familiarise yourself with the relevant data structures (heaps of different descriptions etc. see the wiki)

lots of algorithms for such things:

http://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms

I think this is a bit more complicated than TSP. You want to minimize both the distance and the shuttles used.

How to weight each one? If you only want to minimize shuttle transfers, use sets

Each route is a set. if a set has an item (station or a given letter) that also belongs to another set, you can transfer from one set to another (or from on shuttle to another).

This is something routinely dealt with in transportation planning.

Augment the graph representing the network this way:

1. Use separate links for each route. Give a cost to each (travel time is a good value).
2. Add links between the route links and the nodes representing the stations. Those will represent boarding and alightment.
3. Add a high cost to the boarding links (it doesn't have to be a real cost).

Now the minimum path between two stations will be of cost:

1. One boarding tariff plus the small tariff per link in the path when both stations are connected by a route.
2. Two or more boarding tariffs plus the per-link tariff for stations not directly connected by a route.
3. Infinite if no path between the stations is found.

In all cases, the path will be the minimum with regard to boardings and transfers, and number of links.

Note that every link must have a cost (even if its symbolic) because some path-search algorithms will loop indefinitely if sub-paths of zero cost are allowed.

This is a component of the Traveling Salesman Problem. In effect, there is no "easy" solution. But there are several algorithms which give "good enough" solutions.