All pair shortest path problem for large number of nodes
Search papers on : "Shortest Path Queries Using Highway Hierarchies". There is a paper by Sanders and Schultes. If you follow their citations, there are lot of other papers. These methods are very useful for real road networks.