Shortest path problem where edge weight depends on path taken

Question

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.

Answer 1

Don't do that. Instead, change the way you model the problem as a graph problem.

One crude approach: Rather than having a vertex for each bus stop, introduce one vertex for each pair of a bus stop and a time. For instance, if $s$ is a bus stop and $t$ is a time, then $(s,t)$ is a vertex. If we have a bus that goes from $s$ to $s'$, takes 5 minutes, and departs every 20 minutes, then we'd have edges $(s,0) \to (s',5)$, $(s,20) \to (s',25)$, $(s,40) \to (s',45)$, etc. You can take it from here. (Test for understanding: see if you can work out what the running time of finding the shortest path to some destination is.)

A smarter approach: Fix an original vertex $v_0$ (the starting point of all trips). For each vertex $v$, compute $d(v)$, which is the time it takes to get from $v_0$ to $v$. How do you compute $d(v)$? Use dynamic programming. If you know $d(u)$ for all predecessors $u$ of $v$, then you should be able to work out an easy way to compute $d(v)$. Also, if you've studied shortest-paths algorithms, you should be able to find an ordering for assigning $d(\cdot)$ values. This will provide an efficient algorithm.