From Dewford Town, head north to reach Route 106. You can only explore a small portion of the area until you get Surf. The entrance to the Granite Cave is located to the left. Before entering, you can battle a couple of fishermen here by talking to them and getting in the Backpacker's line of sight. There's also a Protein along the shore, southwest of Fisherman Elliot's location. That's all you can do in this route for the meantime so backtrack a bit and enter the Granite Cave.
Backpacker Graeme (Prize Money: P312)
Fisherman Ned (Prize Money: P416)
Fisherman Elliot (Prize Money: P384)