You could use pretty much any pathfinding algorithm (A* for example) even if you don't have a grid based graph.
In the implementation, you would just need to modify how the algorithm transverses each valid walkable/unwalkable node (how to go from waypoint to waypoint) and possibly how much extra cost each node has (water/mountainous terrain could have increased cost for example) instead of letting it go the usual up/down/left/right and possibly diagonals for grids.
If the waypoint based approach isn't ideal for you, then you should look up "navigation mesh" [1] pathing which is a bit trickier to implement but works well when you have a bunch of large empty/walkable areas.
Directions algorithms on real life maps are quite different from what they teach you in CS classes. Just think of the amount of computation to get the best directions between SF and NYC, taking traffic into consideration. I'm pretty sure none of the services actually give you the best solution, but something that's pretty close to it.
Full USA map graph contains around 24 million nodes, 58 million edges. Your regular A* just doesn't cut it.
A* runs faster if you have better path cost estimates. To get the shortest paths, you want an estimate that's as close to the true cost, but not greater than it. You can precalculate to generate good estimates. Traffic makes the costs higher than normal, so those precalculated estimates are still useable (if you raise the costs because of traffic, the estimates continue to be lower than the true cost), and still much better than what you get without precalculation.
