Shortest path from one vertex to another in a directed graph

Question

My graph is directed and very large. The vertices in the graph represent towns, and the edges represents bus travel routes from town to town. The goal is to find a path from one vertex to another. It is very important that the algorithm takes into account the transfer time between buses.

I would use Dijkstra's algorithm, but it goes from the whole graph and finds one way. I need to find a few of "the best" ways from vertex to vertex. By "the best" I mean with the shortest transfer times, but this is not the most important point.

Answer 1

If you needs to find more than one shortest paths, refers to this question.

Answer 2

The "transfer time" for changing buses is an important variable and would be easiest to express as extra vertices in the graph. Assuming the weights on the edges represent travel times between buses, you can also use nodes and edges to represent transfer time between two buses.

Answer 3

im not sure with transfer term, but there are time dependent highway hierarchy work done by many like goldberg , sanders etc, you can search that on google(dblp, or on any scientific e-lib). For continent size static datasets they are thousands of time faster and are for both dynamic and static scenarios.