I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between stops.
The weights of the edges represents how long it takes to complete a particular journey between stops. For example, if the next bus for a particular route is 10 minutes away, and the journey takes 5 minutes, then the edge weight for that route would be 15.
However, in order to know the amount of time until a particular bus arrives at a stop, it is necessary to know the current time—defined as the sum of the weights of the edges previously taken, plus the time at which the journey started.
What algorithm would allow me to know what vertices have been previously visited, so I can compute the sum of the edge weights? Obviously I could compute every single possible path in the graph, but that seems terribly inefficient.