I am a little suprised to not see Floyd Warshall's algorithm mentioned here. This algorithm work's very much like Dijkstra's. It also has one very nice features which is it allows you to compute as long as you would like to continue allowing more intermediate vertices. So it will naturally find the routes which use interstates or highways fairly quickly.

I am a little suprised to not see Floyd Warshall's algorithm mentioned here. This algorithm work's very much like Dijkstra's. It also has one very nice feature which is it allows you to compute as long as you would like to continue allowing more intermediate vertices. So it will naturally find the routes which use interstates or highways fairly quickly.