Hacker News Reader

Comment by michaelt | Hacker News Reader

  I don't know why they do it

If you represent every edge on the transport graph with a single fixed traversal cost, you can calculate the lowest cost route between two nodes with well known algorithms like (simple) Dijkstra's algorithm or (high performance) Contraction Hierarchies.

When the cost of a route varies with time of day, and the best route changes with time of day, things get quite a bit more complicated.

View on HN

Not as complicated as you might think. You essentially add time as an extra dimension to your graph, true, but because you're dealing with discrete vehicles instead of a continuously varying function, you can take shortcuts that make that portion of it pretty simple. It's the walk to and from the transit stops, in my experience, that's a PITA to deal with when you're trying to do transit routing.

If you're doing simple Dijkstra and you only want to return a result for a single departure time, you're right that it's not too complicated as you still only have one cost per edge.

If you want to do computations in advance, as you need to for fast algorithms like Contraction Hierarchies, you have a cost-vs-time profile for each edge. Things can get complicated quickly.

Reply on news.ycombinator.com