Sample graph dataset for testing algorithms
The Stanford Large Network Dataset Collection appears to include a few weighted graphs. Unfortunately the road networks are apparently unweighted - I'm not sure if shortest-paths is motivated on any of the weighted graphs there.