I have a graph extracted from an American city: vertices represent road intersections, edges/arcs represent road segments connecting the intersections. For each road segment, I have the length and allowed driving speed. Furthermore, roads belong to different classes such as highway/residential/primary roads/....
I am looking for a routing algorithm which does the following:
- Compute a pairwise travel time matrix for each intersection (i.e how long it would take to travel from intersection i to intersection j.
- Query the quickest route from intersection i to j and returns a path (sequence of edges/arcs).
- The algorithm should be able to take updates into consideration. For instance, if there is a congestion on road segment (x,y) which increases its anticipated travel time, or if road segment (x,y) becomes blocked, the data structures should be updated incrementally, thereby updating all affected shortest paths (i.e. update all shortest paths through (x,y)).
The distance matrix will be queried very often so this should be precomputed, but the actual shortest paths can be computed at a later stage if that's more efficient. The number of nodes in the graph is roughly 5000-10000.
I was hoping that people could refer me to literature about this, preferably something that doesn't take weeks to implement. Obviously, simply running Dijkstra for each intersection takes too long. Running Floyd–Warshall all-pairs shortest path algorithm could be a possibility, but I'm not so sure how to update the result if the cost of one of the edges/arcs changes. Furthermore, it seems to be a slow approach since the algorithm ignores that most of the routes go through a small subset of the road segments.
I'm not necessarily looking for an exact approach. A good approximation suffices. Any pointers to literature or algorithm descriptions are welcome. I presume that any kind of routing software needs a similar algorithm. I'm mainly interested in something that works; it shouldn't necessarily be state of the art.
If this isn't the right place to ask, please let me know (especially if you know a better place :) ). Just to emphasize: I'm not looking for a software/database package, I'm looking for an algorithm.